Data Structures公開課聽課筆記-（三）哈希

第三周講的是Hash。

hash的思想是把一個不確定範圍映射到一個確定的範圍，來提高空間和時間的效率。

為什麼要Hash

思考一個簡單的問題，給出一份通話紀律，在通話記錄中，統計所有電話號碼的通話次數。

#phone_list: 通話記錄，每一行是一個電話號碼n1515077n1515081n1515092n2515093n

• direct addressing

假設電話號碼是一個7位數，我們如果直接用數組存儲每個電話號碼的通話次數，用電話號碼所對應的整數做數組下標。可能會得到下面的偽代碼。

#phone_record[]: 通話次數，用數組存儲，數組所有元素初始化為0nfor phone_number in phone_list:n phone_record[ phone_number ] = phone_record[ phone_number ]+1n

電話號碼為7位，所以phone_record數組的長度也是7位（0000000～9999999），而實際在通話記錄中出現的可能只有幾千個不重複的電話號碼，那麼phone_record這個數組99%的空間都是浪費的。

• list－based addressing

那麼有沒有一種方法能夠只存儲出現過的不重複的電話號碼呢，很直接的我們就想到了鏈表。

用一個鏈表來存儲所有出現過的電話號碼，我們可能會得到下面的偽代碼。

#phone_record：通話次數，用鏈表存儲nfor phone_number in phone_list:n if phone_number in phone_record:n phone_record[phone_number] = phone_record[phone_number] + 1n else:n phone_record.append(phone_number)n phone_record[phone_number] = 1n

但是我們都知道，鏈表的查詢效率是O(n)，而數組的查詢效率是O（1），但是會浪費很多時間，那麼怎麼在保證時間和空間都高效的情況下統計通話次數呢，其實問題的關鍵在於通話記錄中的電話號碼是一個不確定的範圍，如果我們可以把這些不確定的電話號碼映射到一個確定的範圍上，就可以解決這個問題。

Hash function

怎麼把電話號碼映射到一個確定的有限的範圍，例如我們的通話記錄中可能有1000個不同的電話號碼，我們首先想到的就是把電話號碼映射成一個3位數。

如何把電話號碼映射成一個三位數呢，可能使用號碼的前三位，我們可以把號碼的前三位存儲在一個000～999的數組裡，數組中的每個下標對應的元素是一個鏈表，存儲前三位是下標的電話號碼的通話次數。

在這種情況中，取電話號碼的前三位就是一個Hash function，它把電話號碼從一個不確定範圍的7位數映射成了一個0～999之間的確定範圍的數字。查找一個電話號碼的時間複雜度取決於最長的鏈表的長度。

但是電話號碼前三位可能表示區號，相同的幾率很大，這樣就會出現有的鏈表很長，而大多數鏈表是空的。

對一個Hash function來說，可能要考慮的參數有以下幾個。

#n：總共有多少個電話號碼n#m：Hash function映射到的範圍大小n#c：最長的鏈表的長度n#所需要的空間複雜度是O（n＋m）n#n／m n#查詢的時間複雜度是O（c）n

因此從空間和時間的角度，我們應該使m和c盡量的小，通常n／m 在 0.5～1之間比較合適。例如對電話號碼來說一個可能的Hash function是

#(10000099-phone_number) mod 1000n

一個好的Hash function能夠使源數據均勻地分布在所映射的範圍內，從而使空間效率和時間效率都儘可能的高。

所有的hash function都是確定（deterministic）的，也就是一定要映射到一個確定的範圍上，不然就失去了Hash的意義。

動態Hash

和動態數組的思想類似，在剛開始時，可能並不知道n是多少，因此在當前的n不夠用的時候就需要增加n的大小並且重新Hash。

字元串的Hash

字元串的Hash最簡單的可以採用多項式的方式，把每一個字母轉換成一個整數，一個字元串看成一個多項式。例如對於abc

a轉換為1，b轉換為2，給出一個x的值，就可以用這個Hash function求出字元串Hash後的值。但這只是一個極其極其簡化的Hash函數。

Rabin-Karp演算法

在一個字元串中匹配一個子串

字元串長：m

子串長：n

大家都非常熟悉的演算法是KMP演算法，複雜度是O（n＋m），課程里介紹了一個基於Hash思想的 Rabin-Karp演算法，複雜度同樣是O（n＋m）

最普通的字元串匹配演算法時間複雜度是O（m*n），我們首先用Hash的思想來處理字元串，對於要查找的字元串m，總共有m－n＋1個長度為n的字元串，我們可以用一個Hash function來計算出這m－n＋1個字元串的Hash值，和子字元串n的Hash值比較，如果Hash function選擇的恰當，那麼這兩個Hash值相同的字元串很有可能就是相同的，我們再檢查這兩個字元串是否相同，如果相同，就找到了一個匹配的子串。

#定義M[i,j]為字元串M從i開始到j的子字元串n#M:要查找的字元串，長度為mn#N：子字元串，長度為nnHash_n = Hash(N)nfor i in range(0, m-n):n if Hash(M[i,i+n-1]) == Hash_n:n if isEqual(N,M[i,i+n-1]):n #find subsequencen

計算m－n＋1個字元串的Hash值的複雜度是O（n），需要計算m－n＋1次。

需要計算長度為n的子字元串的Hash值一次，因此整個演算法的時間複雜度是O（n＊m）。

所以需要考慮，有沒有辦法能夠降低時間複雜度

假如要查找的字元串M為abcde，Hash function用上面提到過的字元串Hash方式，那麼 子串M［1，3］的Hash值是 2+3*x＋4*x^2，而M［0，2］的Hash值是1+2*x＋3*x^2。

我們可以發現M［0，2］的Hash值是可以用 M［1，3］的Hash值表示出來的。

核心的思想在於，M［i，j］這個子串的Hash值，是可以用M［i＋1，j＋1］子串的Hash值在O（1）的時間內計算出來，那麼對於m－n＋1個子串，只需要計算出M［m－n，m］這個子串的Hash值，其他的子串Hash值可以在O（1）＊m也就是O（m）的時間內計算出來。

因此計算M的所有m－n＋1個子字元串的Hash值複雜度為O（n＋m），整體的字元串匹配演算法的複雜度也就是O（n＋m）。
推薦閱讀：