【資料結構】Double hashing是什麼?

雙雜湊（Double Hashing）是一種用於哈希表的碰撞解決方法，透過使用兩個不同的雜湊函數來決定儲存位置，達到均勻分佈資料的效果。當發生碰撞時，雙雜湊法不僅計算初始位置，還會根據第二個雜湊函數計算出「探查步長」，以此找到新的空槽來存放資料。

雙雜湊的運作方式

1. 初始位置計算：使用第一個雜湊函數（如 h1(key)）計算出鍵值 key 在哈希表中的初始位置。
2. 探查步長計算：當發生碰撞時，使用第二個雜湊函數（如 h2(key)）來計算探查步長，使得每個鍵值有唯一的探查序列。
3. 位置計算公式：當發生碰撞時，新位置會按以下公式計算：
   [
   \text{新位置} = (\text{初始位置} + i \times h2(\text{key})) \% \text{表大小}
   ]
   其中，i 是探查次數，每次碰撞會遞增。

雙雜湊的優點

• 降低群聚現象：相比線性探查和平方探查，雙雜湊法提供了一個更獨特的探查步長，使項目更均勻地分佈在表中。
• 高效利用空槽：因為探查步長是依據 key 計算的，即使多次碰撞，每個鍵值的探查序列都不同，避免了重複探查同樣的位置。

例子

假設有一個哈希表大小為 11（質數），我們使用以下的兩個雜湊函數：

1. h1(key) = key % 11（用於計算初始位置）
2. h2(key) = 7 - (key % 7)（用於計算探查步長）

對於鍵值 key = 50：

• 初始位置：h1(50) = 50 % 11 = 6
• 若位置 6 被佔用，則探查步長為 h2(50) = 7 - (50 % 7) = 7 - 1 = 6
• 下次探查位置為 (6 + 1 * 6) % 11 = 1，依此類推

雙雜湊的效率和哈希表大小是否為質數有密切關係，建議將哈希表的大小設為質數，以確保探查步長與表大小互質，避免無限循環。

參考資料

1. 資料結構學習筆記：雜湊表（Hash Table）

本文由 ChatGPT 產生