別眨眼網

一、前言

雜湊錶的歷史

雜湊雜湊的想法在不同的地方獨立出現。1953 年 1 月，漢斯·彼得·盧恩 （ Hans Peter Luhn ） 編寫了一份IBM內部備忘錄，其中使用了雜湊和連結。開放定址後來由 AD Linh 在 Luhn 的論文上提出。大約在同一時間，IBM Research的Gene Amdahl、Elaine M。 McGraw、Nathaniel Rochester和Arthur Samuel為IBM 701彙編器實現了雜湊。 線性探測的開放定址歸功於 Amdahl，儘管Ershov獨立地有相同的想法。“開放定址”一詞是由W。 Wesley Peterson在他的文章中創造的，該文章討論了大檔案中的搜尋問題。

二、雜湊資料結構

雜湊表的存在是為了解決能透過O（1）時間複雜度直接索引到指定元素。

這是什麼意思呢？透過我們使用陣列存放元素，都是按照順序存放的，當需要獲取某個元素的時候，則需要對陣列進行遍歷，獲取到指定的值。如圖所示；

而這樣透過迴圈遍歷比對獲取指定元素的操作，時間複雜度是O（n），也就是說如果你的業務邏輯實現中存在這樣的程式碼是非常拉胯的。那怎麼辦呢？這就引入了雜湊散列表的設計。

在計算機科學中，一個雜湊表（hash table、hash map）是一種實現關聯陣列的抽象資料結構，該結構將鍵透過雜湊計算對映到值。

也就是說我們透過對一個 Key 值計算它的雜湊並與長度為2的n次冪的陣列減一做與運算，計算出槽位對應的索引，將資料存放到索引下。那麼這樣就解決了當獲取指定資料時，只需要根據存放時計算索引ID的方式再計算一次，就可以把槽位上對應的資料獲取處理，以此達到時間複雜度為O（1）的情況。如圖所示；

雜湊雜湊雖然解決了獲取元素的時間複雜度問題，但大多數時候這只是理想情況。因為隨著元素的增多，很可能發生雜湊衝突，或者雜湊值波動不大導致索引計算相同，也就是一個索引位置出現多個元素情況。如圖所示；

當李二狗、拎瓢衝都有槽位的下標索引03的 叮襠貓 發生衝突時，情況就變得糟糕了，因為這樣就不能滿足O（1）時間複雜度獲取元素的訴求了。

那麼此時就出現了一系列解決方案，包括；HashMap 中的拉鍊定址 + 紅黑樹、擾動函式、負載因子、ThreadLocal 的開放定址、合併雜湊、杜鵑雜湊、跳房子雜湊、羅賓漢雜湊等各類資料結構設計。讓元素在發生雜湊衝突時，也可以存放到新的槽位，並儘可能保證索引的時間複雜度小於O（n）

三、實現雜湊雜湊

雜湊雜湊是一個非常常見的資料結構，無論是我們使用的 HashMap、ThreaLocal 還是你在刷題中位了提升索引效率，都會用到雜湊雜湊。

只要雜湊桶的長度由負載因子控制的合理，每次查詢元素的平均時間複雜度與桶中儲存的元素數量無關。另外許多雜湊表設計還允許對鍵值對的任意插入和刪除，每次操作的攤銷固定平均成本。

好，那麼介紹了這麼多，小傅哥帶著大家做幾個關於雜湊雜湊的資料結構，透過實踐來了解會更加容易搞懂。

原始碼地址：https：//github。com/fuzhengwei/java-algorithms （opens new window）-Java 演算法與資料結構

本章原始碼：https：//github。com/fuzhengwei/java-algorithms/blob/main/data-structures/src/main/java/cn/bugstack/algorithms/data/queue/DelayQueue。java（opens new window）

1。 雜湊碰撞

說明：透過模擬簡單 HashMap 實現，去掉拉鍊定址等設計，驗證元素哈新索引位置碰撞。

public class HashMap01 implements Map { private final Object［］ tab = new Object［8］； @Override public void put（K key， V value） { int idx = key。hashCode（） & （tab。length - 1）； tab［idx］ = value； } @Override public V get（K key） { int idx = key。hashCode（） & （tab。length - 1）； return （V） tab［idx］； }}

HashMap01 的實現只是透過雜湊計算出的下標，雜湊存放到固定的陣列內。那麼這樣當發生元素下標碰撞時，原有的元素就會被新的元素替換掉。

測試

@Testpublic void test_hashMap01（） { Map map = new HashMap01<>（）； map。put（“01”， “花花”）； map。put（“02”， “豆豆”）； logger。info（“碰撞前 key：{} value：{}”， “01”， map。get（“01”））； // 下標碰撞 map。put（“09”， “蛋蛋”）； map。put（“12”， “苗苗”）； logger。info（“碰撞前 key：{} value：{}”， “01”， map。get（“01”））；}

06：58：41。691 ［main］ INFO cn。bugstack。algorithms。test。AlgorithmsTest - 碰撞前 key：01 value：花花06：58：41。696 ［main］ INFO cn。bugstack。algorithms。test。AlgorithmsTest - 碰撞前 key：01 value：苗苗Process finished with exit code 0

透過測試結果可以看到，碰撞前 map。get（“01”） 的值是花花，兩次下標索引碰撞後存放的值則是苗苗

這也就是使用雜湊雜湊必須解決的一個問題，無論是在已知元素數量的情況下，透過擴容陣列長度解決，還是把碰撞的元素透過連結串列存放，都是可以的。

2。 拉鍊定址

說明：既然我們沒法控制元素不碰撞，但我們可以對碰撞後的元素進行管理。比如像 HashMap 中拉鍊法一樣，把碰撞的元素存放到連結串列上。這裡我們就來簡化實現一下。

public class HashMap02BySeparateChaining implements Map { private final LinkedList>［］ tab = new LinkedList［8］； @Override public void put（K key， V value） { int idx = key。hashCode（） & （tab。length - 1）； if （tab［idx］ == null） { tab［idx］ = new LinkedList<>（）； tab［idx］。add（new Node<>（key， value））； } else { tab［idx］。add（new Node<>（key， value））； } } @Override public V get（K key） { int idx = key。hashCode（） & （tab。length - 1）； for （Node kvNode ： tab［idx］） { if （key。equals（kvNode。getKey（））） { return kvNode。value； } } return null； } static class Node { final K key； V value； public Node（K key， V value） { this。key = key； this。value = value； } public K getKey（） { return key； } public V getValue（） { return value； } }}

因為元素在存放到雜湊桶上時，可能發生下標索引膨脹，所以這裡我們把每一個元素都設定成一個 Node 節點，這些節點透過 LinkedList 連結串列關聯，當然你也可以透過 Node 節點構建出連結串列 next 元素即可。

那麼這時候在發生元素碰撞，相同位置的元素就都被存放到連結串列上了，獲取的時候需要對存放多個元素的連結串列進行遍歷獲取。

測試

@Testpublic void test_hashMap02（） { Map map = new HashMap02BySeparateChaining<>（）； map。put（“01”， “花花”）； map。put（“05”， “豆豆”）； logger。info（“碰撞前 key：{} value：{}”， “01”， map。get（“01”））； // 下標碰撞 map。put（“09”， “蛋蛋”）； map。put（“12”， “苗苗”）； logger。info（“碰撞前 key：{} value：{}”， “01”， map。get（“01”））；}

07：21：16。654 ［main］ INFO cn。bugstack。algorithms。test。AlgorithmsTest - 碰撞前 key：01 value：花花07：22：44。651 ［main］ INFO cn。bugstack。algorithms。test。AlgorithmsTest - 碰撞前 key：01 value：花花Process finished with exit code 0

此時第一次和第二次獲取01位置的元素就都是花花了，元素沒有被替代。因為此時的元素是被存放到連結串列上了。

3。 開放定址

說明：除了對雜湊桶上碰撞的索引元素進行拉鍊存放，還有不引入新的額外的資料結構，只是在雜湊桶上存放碰撞元素的方式。它叫開放定址，也就是 ThreaLocal 中運用斐波那契雜湊+開放定址的處理方式。

public class HashMap03ByOpenAddressing implements Map { private final Node［］ tab = new Node［8］； @Override public void put（K key， V value） { int idx = key。hashCode（） & （tab。length - 1）； if （tab［idx］ == null） { tab［idx］ = new Node<>（key， value）； } else { for （int i = idx； i < tab。length； i++） { if （tab［i］ == null） { tab［i］ = new Node<>（key， value）； break； } } } } @Override public V get（K key） { int idx = key。hashCode（） & （tab。length - 1）； for （int i = idx； i < tab。length； i ++）{ if （tab［idx］ ！= null && tab［idx］。key == key） { return tab［idx］。value； } } return null； } static class Node { final K key； V value； public Node（K key， V value） { this。key = key； this。value = value； } }}

開放定址的設計會對碰撞的元素，尋找雜湊桶上新的位置，這個位置從當前碰撞位置開始向後尋找，直到找到空的位置存放。

在 ThreadLocal 的實現中會使用斐波那契雜湊、索引計算累加、啟發式清理、探測式清理等操作，以保證儘可能少的碰撞。

測試

@Testpublic void test_hashMap03（） { Map map = new HashMap03ByOpenAddressing<>（）； map。put（“01”， “花花”）； map。put（“05”， “豆豆”）； logger。info（“碰撞前 key：{} value：{}”， “01”， map。get（“01”））； // 下標碰撞 map。put（“09”， “蛋蛋”）； map。put（“12”， “苗苗”）； logger。info（“碰撞前 key：{} value：{}”， “01”， map。get（“01”））；}

07：20：22。382 ［main］ INFO cn。bugstack。algorithms。test。AlgorithmsTest - 碰撞前 key：01 value：花花07：20：22。387 ［main］ INFO cn。bugstack。algorithms。test。AlgorithmsTest - 碰撞前 key：01 value：花花07：20：22。387 ［main］ INFO cn。bugstack。algorithms。test。AlgorithmsTest - 資料結構：HashMap{tab=［null，{“key”：“01”，“value”：“花花”}，{“key”：“09”，“value”：“蛋蛋”}，{“key”：“12”，“value”：“苗苗”}，null，{“key”：“05”，“value”：“豆豆”}，null，null］}Process finished with exit code 0

透過測試結果可以看到，開放定址對碰撞元素的定址存放，也是可用解決雜湊索引衝突問題的。

4。 合併雜湊

說明：合併雜湊是開放定址和單獨連結的混合，碰撞的節點在雜湊表中連結。此演算法適合固定分配記憶體的雜湊桶，透過存放元素時識別雜湊桶上的最大空槽位來解決合併雜湊中的衝突。

public class HashMap04ByCoalescedHashing implements Map { private final Node［］ tab = new Node［8］； @Override public void put（K key， V value） { int idx = key。hashCode（） & （tab。length - 1）； if （tab［idx］ == null） { tab［idx］ = new Node<>（key， value）； return； } int cursor = tab。length - 1； while （tab［cursor］ ！= null && tab［cursor］。key ！= key） { ——cursor； } tab［cursor］ = new Node<>（key， value）； // 將碰撞節點指向這個新節點 while （tab［idx］。idxOfNext ！= 0）{ idx = tab［idx］。idxOfNext； } tab［idx］。idxOfNext = cursor； } @Override public V get（K key） { int idx = key。hashCode（） & （tab。length - 1）； while （tab［idx］。key ！= key） { idx = tab［idx］。idxOfNext； } return tab［idx］。value； } static class Node { final K key； V value； int idxOfNext； public Node（K key， V value） { this。key = key； this。value = value； } }}

合併雜湊的最大目的在於將碰撞元素連結起來，避免因為需要尋找碰撞元素所發生的迴圈遍歷。也就是A、B元素存放時發生碰撞，那麼在找到A元素的時候可以很快的索引到B元素所在的位置。

測試

07：18：43。613 ［main］ INFO cn。bugstack。algorithms。test。AlgorithmsTest - 碰撞前 key：01 value：花花07：18：43。618 ［main］ INFO cn。bugstack。algorithms。test。AlgorithmsTest - 碰撞前 key：01 value：苗苗07：18：43。619 ［main］ INFO cn。bugstack。algorithms。test。AlgorithmsTest - 資料結構：HashMap{tab=［null，{“idxOfNext”：7，“key”：“01”，“value”：“花花”}，null，null，null，{“idxOfNext”：0，“key”：“05”，“value”：“豆豆”}，{“idxOfNext”：0，“key”：“12”，“value”：“苗苗”}，{“idxOfNext”：6，“key”：“09”，“value”：“蛋蛋”}］}Process finished with exit code 0

相對於直接使用開放定址，這樣的掛在鏈路指向的方式，可以提升索引的效能。因為在實際的資料儲存上，元素的下一個位置不一定空元素，可能已經被其他元素佔據，這樣就增加了索引的次數。所以使用直接指向地址的方式，會更好的提高索引效能。

5。 杜鵑雜湊

說明：這個名字起的比較有意思，也代表著它的資料結構。杜鵑鳥在孵化：hatching_chick：的時候，雛鳥會將其他蛋或幼崽推出巢穴；類似的這個資料結構會使用2組key雜湊表，將衝突元素推到另外一個key雜湊表中。

private V put（K key， V value， boolean isRehash） { Object k = maskNull（key）； if （containsKey（k）） { return null； } if （insertEntry（new Entry（（K） k， value））） { if （！isRehash） { size++； } return null； } rehash（2 * table。length）； return put（（K） k， value）；}private boolean insertEntry（Entry e） { int count = 0； Entry current = e； int index = hash（hash1， current。key）； while （current ！= e || count < table。length） { Entry temp = table［index］； if （temp == null） { table［index］ = current； return true； } table［index］ = current； current = temp； if （index == hash（hash1， current。key）） { index = hash（hash2， current。key）； } else { index = hash（hash1， current。key）； } ++count； } return false；}

當多個鍵對映到同一個單元格時會發生這種情況。杜鵑雜湊的基本思想是透過使用兩個雜湊函式而不是僅一個雜湊函式來解決衝突。

這為每個鍵在雜湊表中提供了兩個可能的位置。在該演算法的一種常用變體中，雜湊表被分成兩個大小相等的較小的表，每個雜湊函式都為這兩個表之一提供索引。兩個雜湊函式也可以為單個表提供索引。

在實踐中，杜鵑雜湊比線性探測慢約 20-30%，線性探測是常用方法中最快的。然而，由於它對搜尋時間的最壞情況保證，當需要實時響應率時，杜鵑雜湊仍然很有價值。杜鵑雜湊的一個優點是它的無連結列表屬性，非常適合 GPU 處理。

測試

07：52：04。010 ［main］ INFO cn。bugstack。algorithms。test。AlgorithmsTest - 碰撞前 key：01 value：花花07：52：04。016 ［main］ INFO cn。bugstack。algorithms。test。AlgorithmsTest - 碰撞前 key：01 value：苗苗07：52：04。016 ［main］ INFO cn。bugstack。algorithms。test。AlgorithmsTest - 資料結構：{01=花花， 12=苗苗， 05=豆豆， 09=蛋蛋}Process finished with exit code 0

從測試結果可以看到，杜鵑雜湊可以透過兩個雜湊函式解決索引衝突問題。不過這個探測的過程比較耗時。

6。 跳房子雜湊

說明：跳房子雜湊是一種基於開放定址的演算法，它結合了杜鵑雜湊、線性探測和連結的元素，透過桶鄰域的概念——任何給定佔用桶周圍的後續桶，也稱為“虛擬”桶。 該演算法旨在在雜湊表的負載因子增長超過 90% 時提供更好的效能；它還在併發設定中提供了高吞吐量，因此非常適合實現可調整大小的併發雜湊表。

public boolean insert（AnyType x） { if （！isEmpty（）） { return false； } int currentPos = findPos（x）； if （currentPos == -1） { return false； } if （array［currentPos］ ！= null） { x = array［currentPos］。element； array［currentPos］。isActive = true； } String hope； if （array［currentPos］ ！= null） { hope = array［currentPos］。hope； x = array［currentPos］。element； } else { hope = “10000000”； } array［currentPos］ = new HashEntry<>（x， hope， true）； theSize++； return true；}

該演算法使用一個包含n 個桶的陣列。對於每個桶，它的鄰域是H個連續桶的小集合（即索引接近原始雜湊桶的那些）。鄰域的期望屬性是在鄰域的桶中找到一個專案的成本接近於在桶本身中找到它的成本（例如，透過使鄰域中的桶落在同一快取行中）。在最壞的情況下，鄰域的大小必須足以容納對數個專案（即它必須容納 log（ n ） 個專案），但平均只能是一個常數。如果某個桶的鄰域被填滿，則調整表的大小。

測試

@Testpublic void test_hashMap06（） { HashMap06ByHopscotchHashing map = new HashMap06ByHopscotchHashing<>（）； map。insert（1）； map。insert（5）； map。insert（9）； map。insert（12）； logger。info（“資料結構：{}”， map）；}

17：10：10。363 ［main］ INFO cn。bugstack。algorithms。test。AlgorithmsTest - 資料結構：HashMap{tab=［null，{“element”：1，“hope”：“11000000”，“isActive”：true}，{“element”：9，“hope”：“00000000”，“isActive”：true}，null，{“element”：12，“hope”：“10000000”，“isActive”：true}，{“element”：5，“hope”：“10000000”，“isActive”：true}，null，null］}Process finished with exit code 0

透過測試可以看到，跳房子雜湊會在其原始雜湊陣列條目中找到，或者在接下來的H-1個相鄰條目之一找到對應的衝突元素。

7。 羅賓漢雜湊

說明：羅賓漢雜湊是一種基於開放定址的衝突解決演算法；衝突是透過偏向從其“原始位置”（即專案被雜湊到的儲存桶）最遠或最長探測序列長度（PSL）的元素的位移來解決的。

public void put（K key， V value） { Entry entry = new Entry（key， value）； int idx = hash（key）； // 元素碰撞檢測 while （table［idx］ ！= null） { if （entry。offset > table［idx］。offset） { // 當前偏移量不止一個，則檢視條目交換位置，entry 是正在檢視的條目，增加現在搜尋的事物的偏移量和 idx Entry garbage = table［idx］； table［idx］ = entry； entry = garbage； idx = increment（idx）； entry。offset++； } else if （entry。offset == table［idx］。offset） { // 當前偏移量與正在檢視的檢查鍵是否相同，如果是則它們交換值，如果不是，則增加 idx 和偏移量並繼續 if （table［idx］。key。equals（key）） { // 發現相同值 V oldVal = table［idx］。value； table［idx］。value = value； } else { idx = increment（idx）； entry。offset++； } } else { // 當前偏移量小於我們正在檢視的我們增加 idx 和偏移量並繼續 idx = increment（idx）； entry。offset++； } } // 已經到達了 null 所在的 idx，將新/移動的放在這裡 table［idx］ = entry； size++； // 超過負載因子擴容 if （size >= loadFactor * table。length） { rehash（table。length * 2）； }}

09、12 和 01 發生雜湊索引碰撞，進行偏移量計算調整。透過最長位置探測碰撞元素位移來處理。

測試

public void test_hashMap07（） { Map map = new HashMap07ByRobinHoodHashing<>（）； map。put（“01”， “花花”）； map。put（“05”， “豆豆”）； logger。info（“碰撞前 key：{} value：{}”， “01”， map。get（“01”））； // 下標碰撞 map。put（“09”， “蛋蛋”）； map。put（“12”， “苗苗”）； logger。info（“碰撞前 key：{} value：{}”， “01”， map。get（“12”））； logger。info（“資料結構：{}”， map）；}

07：34：32。593 ［main］ INFO cn。bugstack。algorithms。test。AlgorithmsTest - 碰撞前 key：01 value：花花09 112 101 109 912 105 507：35：07。419 ［main］ INFO cn。bugstack。algorithms。test。AlgorithmsTest - 碰撞前 key：01 value：苗苗07：35：07。420 ［main］ INFO cn。bugstack。algorithms。test。AlgorithmsTest - 資料結構：HashMap{tab=［null，{“key”：“01”，“offset”：0，“value”：“花花”}，{“key”：“12”，“offset”：1，“value”：“苗苗”}，null，null，{“key”：“05”，“offset”：0，“value”：“豆豆”}，null，null，null，{“key”：“09”，“offset”：0，“value”：“蛋蛋”}，null，null，null，null，null，null］}Process finished with exit code 0

透過測試結果和除錯的時候可以看到，雜湊索引衝突是透過偏向從其“原始位置”（即專案被雜湊到的儲存桶）最遠或最長探測序列長度（PSL）的元素的位移來解決。這塊可以新增斷點除錯驗證。