hashmap底層原理絕對看得懂（Hash算法及HashMap底層實現原理）

2023-10-18 18:20:52 1

哈希表作為一種優秀數據結構

本質上存儲結構是一個數組，輔以鍊表和紅黑樹

數組結構在查詢和插入刪除複雜度方面分別為O(1)和O(n)

鍊表結構在查詢和插入刪除複雜度方面分別為O(n)和O(1)

二叉樹做了平衡 兩者都為O(lgn)

而哈希表兩者都為O(1)

哈希表本質是一種(key,value)結構

由此我們可以聯想到，能不能把哈希表的key映射成數組的索引index呢？

如果這樣做的話那麼查詢相當於直接查詢索引，查詢時間複雜度為O(1)

其實這也正是當key為int型時的做法 將key通過某種做法映射成index，從而轉換成數組結構

1.使用hash算法計算key值對應的hash值h(默認用key對應的hashcode進行計算(hashcode默認為key在內存中的地址)),得到hash值

2.計算該(k,v)對應的索引值index

索引值的計算公式為 index = (h % length) length為數組長度

3.儲存對應的(k,v)到數組中去，從而形成a[index] = node,如果a[index]已經有了結點

即可能發生碰撞，那麼需要通過開放尋址法或拉鏈法(Java默認實現）解決衝突

當然這只是一個簡單的步驟，只實現了數組 實際實現會更複雜

hash表 數組類似下圖

h 通過hash算法計算得到的的一個整型數值

h可以近似看做一個由key的hashcode生成的隨機數，區別在於相同的hashcode生成的h必然相同

而不同的hashcode也可能生成相同h，這種情況叫做hash碰撞，好的hash算法應儘量避免hash碰撞

(ps:hash碰撞只能儘量避免，而無法杜絕,由於h是一個固定長度整型數據,原則上只要有足夠多的輸入，就一定會產生碰撞)

關於hash算法有很多種，這裡不展開贅述，只需要記住h是一個由hashcode產生的偽隨機數即可

同時需要滿足key.hashcode -> h 分布儘量均勻(下文會解釋為何需要分布均勻)

了解更多請私信

由上我們可以知道，不同的hashcode可能導致相應的h即發生碰撞

那麼我們需要把相應的放到hashmap的其他存儲地址

通過在數組以某種方式尋找數組中空餘的結點放置

基本思想是：當關鍵字key的哈希地址p=H（key）出現衝突時

以p為基礎，產生另一個哈希地址p1，如果p1仍然衝突，再以p為基礎，產生另一個哈希地址p2，…，直到找出一個不衝突的哈希地址pi。

通過引入鍊表 數組中每一個實體存儲為鍊表結構，如果發生碰撞，則把舊結點指針指向新鍊表結點，此時查詢碰撞結點只需要遍歷該鍊表即可

在這種方法下，數據結構如下所示

int類型數據 hashcode 為自身值

HashMap 是一個用於存儲Key-Value 鍵值對的集合，每一個鍵值對也叫做Entry。這些個Entry 分散存儲在一個數組當中，這個數組就是HashMap 的主幹。

HashMap 數組每一個元素的初始值都是Null。

調用Put方法的時候發生了什麼呢？

比如調用 hashMap.put(「apple」, 0) ，插入一個Key為「apple」的元素。這時候我們需要利用一個哈希函數來確定Entry的插入位置（index）：

index = Hash（"apple"）

假定最後計算出的index是2，那麼結果如下：

但是，因為HashMap的長度是有限的，當插入的Entry越來越多時，再完美的Hash函數也難免會出現index衝突的情況。比如下面這樣：

這時需要利用鍊表來解決。

HashMap數組的每一個元素不止是一個Entry對象，也是一個鍊表的頭節點。每一個Entry對象通過Next指針指向它的下一個Entry節點。當新來的Entry映射到衝突的數組位置時，只需要插入到對應的鍊表即可：

新來的Entry節點插入鍊表時，使用的是「頭插法。

使用Get方法根據Key來查找Value的時候，發生了什麼呢？

首先會把輸入的Key做一次Hash映射，得到對應的index：

index = Hash（「apple」）

由於剛才所說的Hash衝突，同一個位置有可能匹配到多個Entry，這時候就需要順著對應鍊表的頭節點，一個一個向下來查找。假設我們要查找的Key是「apple」：

第一步，我們查看的是頭節點Entry6，Entry6的Key是banana，顯然不是我們要找的結果。

第二步，我們查看的是Next節點Entry1，Entry1的Key是apple，正是我們要找的結果。

之所以把Entry6放在頭節點，是因為HashMap的發明者認為，後插入的Entry被查找的可能性更大。

初始長度為16，且每次自動擴容或者手動初始化的時候必須是2的冪。

如何進行位運算呢？有如下的公式（Length是HashMap的長度）：

之前說過，從Key映射到HashMap數組的對應位置，會用到一個Hash函數：

index = Hash（「apple」）

如何實現一個儘量均勻分布的Hash函數呢？我們通過利用Key的HashCode值來做某種運算。

index = HashCode（Key） & （Length - 1）

下面我們以值為「book」的Key來演示整個過程：

計算book的hashcode，結果為十進位的3029737，二進位的101110001110101110 1001。

假定HashMap長度是默認的16，計算Length-1的結果為十進位的15，二進位的1111。

把以上兩個結果做與運算，101110001110101110 1001 & 1111 = 1001，十進位是9，所以 index=9。

可以說，Hash算法最終得到的index結果，完全取決於Key的Hashcode值的最後幾位。這裡地位運算其實是一種快速取模算法。

HashMap 的size為什麼必須是2的冪?。這是因為2的冪用二進位表示時所有位都為1，例如16-1=15 的二進位就是1111B。我們說了Hash算法是為了讓hash 的分布變得均勻。其實我們可以把1111看成四個通道，表示跟1111 做&運算後分布是均勻的。假如默認長度取10，二進位表示為1010，這樣就相當於有兩個通道是關閉的，所以計算出來的索引重複的機率比較大。

徹底搞懂下面關於hash內容

了解更多請私信