IT工程師數位筆記本

我們知道，通過對數組進行直接尋址（Direct Addressing），可以在 O(1) 時間內訪問數組中的任意元素。所以，如果存儲空間允許，可以提供一個數組，為每個可能的關鍵字保留一個位置，就可以應用直接尋址技術。

哈希表（Hash Table）是普通數組概念的推廣。當實際存儲的的關鍵字數比可能的關鍵字總數較小時，這時采用哈希表就會比使用直接數組尋址更為有效。因為哈希表通常采用的數組尺寸與所要存儲的關鍵字數是成比例的。

哈希表是一種動態集合數據結構，在一些合理的假設下，在哈希表中查找一個元素的期望時間是 O(1) 。

• 哈希表（Hashtable）
  • 哈希沖突解決策略：開放尋址法（Open Addressing）
    • 線性探查（Linear Probing）
    • 二次探查（Quadratic Probing）
    • 二度哈希（Rehashing）/雙重哈希（Double Hashing）
  • 哈希沖突解決策略：鏈接技術（chaining）
• 哈希函數的設計
  • 除法哈希法（The Division Method）
  • 乘法哈希法（The Multiplication Method）
  • 全域哈希法（Universal Hashing）
• 完美哈希（Perfect Hashing）

哈希表（Hashtable）

現在假設我們要使用員工的社保號作為唯一標識進行存儲。社保號的格式為 DDD-DD-DDDD（D 的范圍為數字 0-9）。

如果使用 Array 存儲員工信息，要查詢社保號為 111-22-3333 的員工，則將會嘗試遍歷數組的所有位置，即執行漸進時間為 O(n) 的查詢操作。好一些的辦法是將社保號排序，以使查詢漸進時間降低到 O(log(n))。但理想情況下，我們更希望查詢漸進時間為 O(1)。

一種方案是建立一個大數組，范圍從 000-00-0000 到 999-99-9999 。

這種方案的缺點是浪費空間。如果我們僅需要存儲 1000 個員工的信息，那么僅利用了 0.0001% 的空間。

第二種方案就是用哈希函數（Hash Function）壓縮序列。

我們選擇使用社保號的后四位作為索引，以減少區間的跨度。這樣范圍將從 0000 到 9999。

在數學上，將這種從 9 位數轉換為 4 位數的方式稱為哈希轉換（Hashing）。可以將一個數組的索引空間（indexers space）壓縮至相應的哈希表（Hash Table）。

在上面的例子中，哈希函數的輸入為 9 位數的社保號，輸出結果為后 4 位。

H(x) = last four digits of x

上圖中也說明在哈希函數計算中常見的一種行為：哈希沖突（Hash Collisions）。即有可能兩個社保號的后 4 位均為 0000。

當要添加新元素到 Hashtable 中時，哈希沖突是導致操作被破壞的一個因素。如果沒有沖突發生，則元素被成功插入。如果發生了沖突，則需要判斷沖突的原因。因此，哈希沖突提高了操作的代價，Hashtable 的設計目標就是要盡可能減低沖突的發生。

處理哈希沖突的方式有兩種：避免和解決，即沖突避免機制（Collision Avoidance）和沖突解決機制（Collision Resolution）。

避免哈希沖突的一個方法就是選擇合適的哈希函數。哈希函數中的沖突發生的幾率與數據的分布有關。例如，如果社保號的后 4 位是隨即分布的，則使用后 4 位數字比較合適。但如果后 4 位是以員工的出生年份來分配的，則顯然出生年份不是均勻分布的，則選擇后 4 位會造成大量的沖突。我們將這種選擇合適的哈希函數的方法稱為沖突避免機制（Collision Avoidance）。

在處理沖突時，有很多策略可以實施，這些策略稱為沖突解決機制（Collision Resolution）。其中一種方法就是將要插入的元素放到另外一個塊空間中，因為相同的哈希位置已經被占用。

哈希沖突解決策略：開放尋址法（Open Addressing）

通常采用的沖突解決策略為開放尋址法（Open Addressing），將所有的元素都存放在哈希表內的數組中，不使用額外的數據結構。

開放尋址法的最簡單的一種實現就是線性探查（Linear Probing），步驟如下：

1. 當插入新的元素時，使用哈希函數在哈希表中定位元素位置；
2. 檢查哈希表中該位置是否已經存在元素。如果該位置內容為空，則插入并返回，否則轉向步驟 3。
3. 如果該位置為 i，則檢查 i+1 是否為空，如果已被占用，則檢查 i+2，依此類推，直到找到一個內容為空的位置。

現在如果我們要將五個員工的信息插入到哈希表中：

• Alice (333-33-1234)
• Bob (444-44-1234)
• Cal (555-55-1237)
• Danny (000-00-1235)
• Edward (111-00-1235)

則插入后的哈希表可能如下：

元素的插入過程：

• Alice 的社保號被哈希為 1234，因此存放在位置 1234。
• Bob 的社保號被哈希為 1234，但由于位置 1234 處已經存放 Alice 的信息，則檢查下一個位置 1235，1235 為空，則 Bob 的信息就被放到 1235。
• Cal 的社保號被哈希為 1237，1237 位置為空，所以 Cal 就放到 1237 處。
• Danny 的社保號被哈希為 1235，1235 已被占用，則檢查 1236 位置是否為空，1236 為空，所以 Danny 就被放到 1236。
• Edward 的社保號被哈希為 1235，1235 已被占用，檢查1236，也被占用，再檢查1237，直到檢查到 1238時，該位置為空，于是 Edward 被放到了1238 位置。

線性探查（Linear Probing）方式雖然簡單，但并不是解決沖突的最好的策略，因為它會導致同類哈希的聚集（Primary Clustering）。這導致搜索哈希表時，沖突依然存在。例如上面例子中的哈希表，如果我們要訪問 Edward 的信息，因為 Edward 的社保號 111-00-1235 哈希為 1235，然而我們在 1235 位置找到的是 Bob，所以再搜索 1236，找到的卻是 Danny，以此類推直到找到 Edward。

一種改進的方式為二次探查（Quadratic Probing），即每次檢查位置空間的步長為平方倍數。也就是說，如果位置 s 被占用，則首先檢查 s + 1² 處，然后檢查s - 1²，s + 2²，s - 2²，s + 3² 依此類推，而不是象線性探查那樣以 s + 1，s + 2 ... 方式增長。盡管如此，二次探查同樣也會導致同類哈希聚集問題（Secondary Clustering）。

另一種改進的開放尋址法稱為二度哈希（Rehashing）（或稱為雙重哈希（Double Hashing））。

二度哈希的工作原理如下：

有一個包含一組哈希函數 H1...Hn 的集合。當需要從哈希表中添加或獲取元素時，首先使用哈希函數 H1。如果導致沖突，則嘗試使用 H2，以此類推，直到 Hn。所有的哈希函數都與 H1 十分相似，不同的是它們選用的乘法因子（multiplicative factor）。

在 .NET 中 Hashtable 類的哈希函數 Hk 的定義如下：

Hk(key) = [GetHash(key) + k * (1 + (((GetHash(key) >> 5) + 1) % (hashsize – 1)))] % hashsize

當使用二度哈希時，重要的是在執行了 hashsize 次探查后，哈希表中的每一個位置都有且只有一次被訪問到。也就是說，對于給定的 key，對哈希表中的同一位置不會同時使用 Hi 和 Hj。在 Hashtable 類中使用二度哈希公式，其始終保持 (1 + (((GetHash(key) >> 5) + 1) % (hashsize – 1)) 與 hashsize 互為素數（兩數互為素數表示兩者沒有共同的質因子）。

二度哈希使用了 Θ(m²) 種探查序列，而線性探查（Linear Probing）和二次探查（Quadratic Probing）使用了Θ(m) 種探查序列，故二度哈希提供了更好的避免沖突的策略。

向 Hashtable 中添加新元素時，需要檢查以保證元素與空間大小的比例不會超過最大比例。如果超過了，哈希表空間將被擴充。步驟如下：

• 哈希表的位置空間幾乎被翻倍。準確地說，位置空間值從當前的素數值增加到下一個最大的素數值。
• 因為二度哈希時，哈希表中的所有元素值將依賴于哈希表的位置空間值，所以表中所有值也需要重新二度哈希。

由此看出，對哈希表的擴充將是以性能損耗為代價。因此，我們應該預先估計哈希表中最有可能容納的元素數量，在初始化哈希表時給予合適的值進行構造，以避免不必要的擴充。

哈希沖突解決策略：鏈接技術（chaining）

鏈接技術（chaining）是一種沖突解決策略（Collision Resolution Strategy）。在鏈接法中，把哈希到同一個槽中的所有元素都放到一個鏈表中。

使用探查技術（probing）時，如果發生沖突，則將嘗試列表中的下一個位置。如果使用二度哈希（rehashing），則將導致所有的哈希被重新計算。而鏈接技術（chaining）將采用額外的數據結構來處理沖突，其將哈希表中每個位置（slot）都映射到了一個鏈表。當沖突發生時，沖突的元素將被添加到桶（bucket）列表中，而每個桶都包含了一個鏈表以存儲相同哈希的元素。

上圖中的哈希表包含了 8 個桶（bucket），也就是自頂向下的黃色背景的位置。如果一個新的元素要被添加至哈希表中，將會被添加至其 Key 的哈希所對應的桶中。如果在相同位置已經有一個元素存在了，則將會將新元素添加到列表的前面。

使用鏈接技術添加元素的操作涉及到哈希計算和鏈表操作，但其仍為常量，漸進時間為 O(1)。而進行查詢和刪除操作時，其平均時間取決于元素的數量和桶（bucket）的數量。具體的說就是運行時間為 O(n/m)，這里 n 為元素的總數量，m 是桶的數量。但通常對哈希表的實現幾乎總是使 n = O(m)，也就是說，元素的總數絕不會超過桶的總數，所以 O(n/m) 也變成了常量 O(1)。

哈希函數的設計

一個好的哈希函數應滿足假設：每個關鍵字都等可能地被哈希到 m 個槽位的任何一個之中，并且與其他的關鍵字已被哈希到哪一個槽位中無關。不幸的是，通常情況下不太可能檢查這一條件是否成立，因為人們很少能知道關鍵字所符合的概率分布，而各關鍵字可能并不是完全互相獨立的。在實踐中，常常運用啟發式技術來構造好的哈希函數。比如在設計中，可以利用有關關鍵字分布的限制性信息等。

除法哈希法和乘法哈希法屬于啟發式的方法，而全域哈希法則采用了隨機化技術來獲取良好的性能。

除法哈希法（The Division Method）

一種好的哈希做法是以獨立于數據中可能存在的任何模式的方式導出哈希值。例如，除法哈希法用一個特定的質數來除所給的關鍵字，所得的余數即為該關鍵字的哈希值。

除法哈希函數可表示為：

hash(key) = key mod m

其中 key 表示被哈希的關鍵字，m 表示哈希表的大小，mod 為取余操作。假定所選擇的質數與關鍵字分布中的任何模式都是無關的，這種方法常常可以給出很好的結果。

乘法哈希法（The Multiplication Method）

乘法哈希函數可表示為：

hash(key) = floor( m * ( A * key mod 1) )

其中 floor 表示對表達式進行下取整，常數 A 取值范圍為（0<A<1），m 表示哈希表的大小，mod 為取余操作。[A * key mod 1] 表示將 key 乘上某個在 0~1 之間的數并取乘積的小數部分，該表達式等價于 [A*key - floor(A * key)]。

乘法哈希法的一個優點是對 m 的選擇沒有什么特別的要求，一般選擇它為 2 的某個冪次，這是因為我們可以在大多數計算機上更方便的實現該哈希函數。

雖然這個方法對任何的 A 值都適用，但對某些值效果更好，最佳的選擇與待哈希的數據的特征有關。Don Knuth 認為 A ≈ (√5-1)/2 = 0.618 033 988... 比較好，可稱為黃金分割點。

全域哈希法（Universal Hashing）

在向哈希表中插入元素時，如果所有的元素全部被哈希到同一個桶中，此時數據的存儲實際上就是一個鏈表，那么平均的查找時間為 Θ(n) 。而實際上，任何一個特定的哈希函數都有可能出現這種最壞情況，唯一有效的改進方法就是隨機地選擇哈希函數，使之獨立于要存儲的元素。這種方法稱作全域哈希（Universal Hashing）。

全域哈希的基本思想是在執行開始時，從一組哈希函數中，隨機地抽取一個作為要使用的哈希函數。就像在快速排序中一樣，隨機化保證了沒有哪一種輸入會始終導致最壞情況的發生。同時，隨機化也使得即使是對同一個輸入，算法在每一次執行時的情況也都不一樣。這樣就確保了對于任何輸入，算法都具有較好的平均運行情況。

hasha,b(key) = ((a*key + b) mod p) mod m

其中，p 為一個足夠大的質數，使得每一個可能的關鍵字 key 都落在 0 到 p - 1 的范圍內。m 為哈希表中槽位數。任意 a∈{1,2,3,…,p-1}，b∈{0,1,2,…,p-1}。

完美哈希（Perfect Hashing）

當關鍵字的集合是一個不變的靜態集合（Static）時，哈希技術還可以用來獲取出色的最壞情況性能。如果某一種哈希技術在進行查找時，其最壞情況的內存訪問次數為 O(1) 時，則稱其為完美哈希（Perfect Hashing）。

設計完美哈希的基本思想是利用兩級的哈希策略，而每一級上都使用全域哈希（Univeral Hashing）。

第一級與使用鏈接技術（chaining）的哈希表基本上是一樣的，利用從某一全域哈希函數族中隨機選擇的一個函數 h ，將 n 個關鍵字哈希到 m 個槽中。

而此時，不像鏈接技術中對槽使用鏈表結構，而是采用一個較小的二次哈希表 S_j ，與其相關的哈希函數為 h_j 。通過隨機的選取哈希函數 h_j ，可以確保在第二級上不出現哈希沖突。

如果利用從一個全域哈希函數族中隨機選擇的哈希函數 h，將 n 個關鍵字存儲在一個大小為 m = n² 的哈希表中，那么出現碰撞的概率小于 1/2 。

為了確保第二級上不出現哈希沖突，需要讓哈希表 S_j 的大小 m_j 為哈希到槽 j 中的關鍵字數 n_j 的平方。m_j 對 n_j 的這種二次依賴關系看上去可能使得總體存儲需求很大，但通過適當地選擇第一次哈希函數，預期使用的的總存儲空間仍為 O(n)。

如果關鍵字的數量 n 等于槽的數量 m ，則該哈希函數稱為最小完美哈希函數（Minimal Perfect Hash Function）。

參考資料

• Hash function
• Universal hashing
• Perfect hash function
• A Practical Minimal Perfect Hashing Method
• An Approach for Minimal Perfect Hash Functions for Very Large Databases
• 常用數據結構及復雜度
• 淺談散列
• 完美哈希函數（Perfect Hash Function）
• gperf--GNU完美哈希函數生成器用戶手冊(翻譯)
• 使用 gperf 實現高效的 C/C++ 命令行處理
• Universal and Perfect Hashing

本文《哈希表和完美哈希》由 Dennis Gao 發表自博客園博客，任何未經作者本人允許的人為或爬蟲轉載均為耍流氓。