HashMap 作為最常用的集合類之一，有必要深入淺出的瞭解一下。這篇文章會深入到 HashMap 源碼，刨析它的存儲結構以及工作機制。

1. HashMap 的存儲結構

HashMap 的數據存儲結構是一個 Node 數組，在（Java 7 中是 Entry 數組，但結構相同）

存儲結構主要是數組加鏈表，像下面的圖。

HashMap 存儲結構(圖片來自網絡)

2. HashMap 的 put()

在 Java 8 中 HashMap 的 put 方法如下，我已經詳細註釋了重要代碼。

舉個例子，如果 put 的 key 為字母 a，當前 HashMap 容量是初始容量 16，計算出位置是 1。

總結 HashMap put 過程。

1. 計算 key 的 hash 值。計算方式是 (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
2. 檢查當前數組是否為空，為空需要進行初始化，初始化容量是 16 ，負載因子默認 0.75。
3. 計算 key 在數組中的座標。計算方式：(容量 - 1) & hash.因為容量總是2的次方，所以-1的值的二進制總是全1。方便與 hash 值進行與運算。
4. 如果計算出的座標元素為空，創建節點加入，put 結束。
1. 如果當前數組容量大於負載因子設置的容量，進行擴容。
5. 如果計算出的座標元素有值。
1. 如果 next 節點為空，把要加入的值和 key 加入 next 節點。
2. 如果 next 節點不為空，循環查看 next 節點。如果發現有 next 節點的 key 和要加入的 key 一樣，對應的值替換為新值。
3. 如果循環 next 節點查找超過8層還不為空，把這個位置元素轉換為紅黑樹。
4. 如果座標上的元素值和要加入的值 key 完全一樣，覆蓋原有值。
5. 如果座標上的元素是紅黑樹，把要加入的值和 key 加入到紅黑樹。
6. 如果座標上的元素和要加入的元素不同（尾插法增加）。

3. HashMap 的 get()

在 Java 8 中 get 方法源碼如下，我已經做了註釋說明。

get 方法流程總結。

1. 計算 key 的 hash 值。
2. 如果存儲數組不為空，且計算得到的位置上的元素不為空。繼續，否則，返回 Null。
3. 如果獲取到的元素的 key 值相等，說明查找到了，返回元素。
4. 如果獲取到的元素的 key 值不相等，查找 next 節點的元素。
1. 如果元素是紅黑樹，在紅黑樹中查找。
2. 不是紅黑樹，遍歷 next 節點查找，找到則返回。

4. HashMap 的 Hash 規則

1. 計算 hash 值 int hash = key.hashCode()。
2. 與或上 hash 值無符號右移16 位。hash = hash ^ (hash >>> 16)。
3. 位置計算公式 index = (n - 1) & hash ，其中 n 是容量。

5. HashMap 的初始化大小

1. 初始化大小是 16，為什麼是 16 呢？這可能是因為每次擴容都是 2 倍。而選擇 2 的次方值 16 作為初始容量，有利於擴容時重新 Hash 計算位置。為什麼是 16 我想是一個經驗值，理論上說只要是 2 的次方都沒有問題。

6. HashMap 的擴容方式

負載因子是多少？負載因子是 0.75。

擴容方式是什麼？看源碼說明。

擴容時候怎麼重新確定元素在數組中的位置，我們看到是由 if ((e.hash & oldCap) == 0) 確定的。

通過上面的分析也可以看出，只有在每次容量都是2的次方的情況下才能使用 if ((e.hash & oldCap) == 0) 判斷擴容後的位置。

7. HashMap 中的紅黑樹

HashMap 在 Java 8 中的實現增加了紅黑樹，當鏈表節點達到 8 個的時候，會把鏈表轉換成紅黑樹，低於 6 個的時候，會退回鏈表。究其原因是因為當節點過多時，使用紅黑樹可以更高效的查找到節點。畢竟紅黑樹是一種二叉查找樹。

1. 節點個數是多少的時候，鏈表會轉變成紅黑樹。鏈表節點個數大於等於 8 時，鏈表會轉換成樹結構。
2. 節點個數是多少的時候，紅黑樹會退回鏈表。節點個數小於等於 6 時，樹會轉變成鏈表。
3. 為什麼轉變條件 8 和 6 有一個差值。如果沒有差值，都是 8 ，那麼如果頻繁的插入刪除元素，鏈表個數又剛好在 8 徘徊，那麼就會頻繁的發生鏈表轉樹，樹轉鏈表。

8. 為啥容量都是2的冪？

容量是2的冪時，key 的 hash 值然後 & (容量-1) 確定位置時碰撞概率會比較低，因為容量為 2 的冪時，減 1 之後的二進制數為全1，這樣與運算的結果就等於 hasｈ值後面與 1 進行與運算的幾位。

下面是個例子。

如果是其他的容量值，假設是9，進行與運算結果碰撞的概率就比較大。

另外，每次都是 2 的冪也可以讓 HashMap 擴容時可以方便的重新計算位置。

9. 快速失敗（fail—fast）

HashMap 遍歷使用的是一種快速失敗機制，它是 Java 非安全集合中的一種普遍機制，這種機制可以讓集合在遍歷時，如果有線程對集合進行了修改、刪除、增加操作，會觸發併發修改異常。

它的實現機制是在遍歷前保存一份 modCount ，在每次獲取下一個要遍歷的元素時會對比當前的 modCount 和保存的 modCount 是否相等。

快速失敗也可以看作是一種安全機制，這樣在多線程操作不安全的集合時，由於快速失敗的機制，會拋出異常。

10. 線程安全的 Map

1. 使用 Collections.synchronizedMap(Map) 創建線程安全的 Map.實現原理：有一個變量 final Object mutex; ，操作方法都加了這個 synchronized (mutex) 排它鎖。
2. 使用 Hashtable
3. 使用 ConcurrentHashMap

閱讀更多 Java技術虎 的文章

關鍵字: 簡潔 解讀 源碼