HashMap 源碼詳細分析(JDK1.8)二

來源：https://www.cnblogs.com/chanshuyi/p/java_collection_hashmap_18.html

嵌套分支：

條件覆蓋情況備註oldCap >= 230桶數組容量大於或等於最大桶容量 230這種情況下不再擴容newCap < 230 && oldCap > 16新桶數組容量小於最大值，且舊桶數組容量大於 16該種情況下新閾值 newThr = oldThr << 1，移位可能會導致溢出

這裡簡單說明一下移位導致的溢出情況，當 loadFactor小數位為 0，整數位可被2整除且大於等於8時，在某次計算中就可能會導致 newThr 溢出歸零。見下圖：

分支二：

條件覆蓋情況備註newThr == 0第一個條件分支未計算 newThr 或嵌套分支在計算過程中導致 newThr 溢出歸零

說完 newCap 和 newThr 的計算過程，接下來再來分析一下鍵值對節點重新映射的過程。

在 JDK 1.8 中，重新映射節點需要考慮節點類型。對於樹形節點，需先拆分紅黑樹再映射。對於鏈表類型節點，則需先對鏈表進行分組，然後再映射。需要的注意的是，分組後，組內節點相對位置保持不變。關於紅黑樹拆分的邏輯將會放在下一小節說明，先來看看鏈表是怎樣進行分組映射的。

我們都知道往底層數據結構中插入節點時，一般都是先通過模運算計算桶位置，接著把節點放入桶中即可。事實上，我們可以把重新映射看做插入操作。在 JDK 1.7 中，也確實是這樣做的。但在 JDK 1.8 中，則對這個過程進行了一定的優化，邏輯上要稍微複雜一些。在詳細分析前，我們先來回顧一下 hash 求餘的過程：

上圖中，桶數組大小 n = 16，hash1 與 hash2 不相等。但因為只有後4位參與求餘，所以結果相等。當桶數組擴容後，n 由16變成了32，對上面的 hash 值重新進行映射：

擴容後，參與模運算的位數由4位變為了5位。由於兩個 hash 第5位的值是不一樣，所以兩個 hash 算出的結果也不一樣。上面的計算過程並不難理解，繼續往下分析。

假設我們上圖的桶數組進行擴容，擴容後容量 n = 16，重新映射過程如下:

依次遍歷鏈表，並計算節點 hash & oldCap 的值。如下圖所示

如果值為0，將 loHead 和 loTail 指向這個節點。如果後面還有節點 hash & oldCap 為0的話，則將節點鏈入 loHead 指向的鏈表中，並將 loTail 指向該節點。如果值為非0的話，則讓 hiHead 和 hiTail 指向該節點。完成遍歷後，可能會得到兩條鏈表，此時就完成了鏈表分組：

最後再將這兩條鏈接存放到相應的桶中，完成擴容。如下圖：

從上圖可以發現，重新映射後，兩條鏈表中的節點順序並未發生變化，還是保持了擴容前的順序。以上就是 JDK 1.8 中 HashMap 擴容的代碼講解。另外再補充一下，JDK 1.8 版本下 HashMap 擴容效率要高於之前版本。如果大家看過 JDK 1.7 的源碼會發現，JDK 1.7 為了防止因 hash 碰撞引發的拒絕服務攻擊，在計算 hash 過程中引入隨機種子。以增強 hash 的隨機性，使得鍵值對均勻分佈在桶數組中。在擴容過程中，相關方法會根據容量判斷是否需要生成新的隨機種子，並重新計算所有節點的 hash。而在 JDK 1.8 中，則通過引入紅黑樹替代了該種方式。從而避免了多次計算 hash 的操作，提高了擴容效率。

本小節的內容講就先講到這，接下來，來講講鏈表與紅黑樹相互轉換的過程。

鏈表樹化、紅黑樹鏈化與拆分

JDK 1.8 對 HashMap 實現進行了改進。最大的改進莫過於在引入了紅黑樹處理頻繁的碰撞，代碼複雜度也隨之上升。比如，以前只需實現一套針對鏈表操作的方法即可。而引入紅黑樹後，需要另外實現紅黑樹相關的操作。紅黑樹是一種自平衡的二叉查找樹，本身就比較複雜。本篇文章中並不打算對紅黑樹展開介紹，本文僅會介紹鏈表樹化需要注意的地方。至於紅黑樹詳細的介紹，如果大家有興趣，可以參考我的另一篇文章 - 紅黑樹詳細分析。

在展開說明之前，先把樹化的相關代碼貼出來，如下：

static final int TREEIFY_THRESHOLD = 8;
/**
 * 當桶數組容量小於該值時，優先進行擴容，而不是樹化
 */
static final int MIN_TREEIFY_CAPACITY = 64;
static final class TreeNode extends LinkedHashMap.Entry {
 TreeNode parent; // red-black tree links
 TreeNode left;
 TreeNode 
 right;
 TreeNode prev; // needed to unlink next upon deletion
 boolean red;
 TreeNode(int hash, K key, V val, Node next) {
 super(hash, key, val, next);
 }
}
/**
 * 將普通節點鏈表轉換成樹形節點鏈表
 */
final void treeifyBin(Node[] tab, int hash) {
 int n, index; Node e;
 // 桶數組容量小於 MIN_TREEIFY_CAPACITY，優先進行擴容而不是樹化
 if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
 resize();
 else if ((e = tab[index = (n - 1) & hash]) != null) {
 // hd 為頭節點（head），tl 為尾節點（tail）
 TreeNode hd = null, tl = null;
 do {
 // 將普通節點替換成樹形節點
 TreeNode p = replacementTreeNode(e, null);
 if (tl == null)
 hd = p;
 else {
 p.prev = tl;
 tl.next = p;
 }
 tl = p;
 } while ((e = e.next) != null); // 將普通鏈表轉成由樹形節點鏈表
 if ((tab[index] = hd) != null)
 // 將樹形鏈表轉換成紅黑樹
 hd.treeify(tab);
 }
}
TreeNode replacementTreeNode(Node 
 p, Node next) {
 return new TreeNode<>(p.hash, p.key, p.value, next);
}

在擴容過程中，樹化要滿足兩個條件：

• 鏈表長度大於等於 TREEIFY_THRESHOLD
• 桶數組容量大於等於 MIN_TREEIFY_CAPACITY

第一個條件比較好理解，這裡就不說了。這裡來說說加入第二個條件的原因，個人覺得原因如下：

當桶數組容量比較小時，鍵值對節點 hash 的碰撞率可能會比較高，進而導致鏈表長度較長。這個時候應該優先擴容，而不是立馬樹化。畢竟高碰撞率是因為桶數組容量較小引起的，這個是主因。容量小時，優先擴容可以避免一些列的不必要的樹化過程。同時，桶容量較小時，擴容會比較頻繁，擴容時需要拆分紅黑樹並重新映射。所以在桶容量比較小的情況下，將長鏈表轉成紅黑樹是一件吃力不討好的事。

回到上面的源碼中，我們繼續看一下 treeifyBin 方法。該方法主要的作用是將普通鏈表轉成為由 TreeNode 型節點組成的鏈表，並在最後調用 treeify 是將該鏈表轉為紅黑樹。TreeNode 繼承自 Node 類，所以 TreeNode 仍然包含 next 引用，原鏈表的節點順序最終通過 next 引用被保存下來。我們假設樹化前，鏈表結構如下：

HashMap 在設計之初，並沒有考慮到以後會引入紅黑樹進行優化。所以並沒有像 TreeMap 那樣，要求鍵類實現 comparable 接口或提供相應的比較器。但由於樹化過程需要比較兩個鍵對象的大小，在鍵類沒有實現 comparable 接口的情況下，怎麼比較鍵與鍵之間的大小了就成了一個棘手的問題。為了解決這個問題，HashMap 是做了三步處理，確保可以比較出兩個鍵的大小，如下：

• 比較鍵與鍵之間 hash 的大小，如果 hash 相同，繼續往下比較
• 檢測鍵類是否實現了 Comparable 接口，如果實現調用 compareTo 方法進行比較
• 如果仍未比較出大小，就需要進行仲裁了，仲裁方法為 tieBreakOrder（大家自己看源碼吧）

tie break 是網球術語，可以理解為加時賽的意思，起這個名字還是挺有意思的。

通過上面三次比較，最終就可以比較出孰大孰小。比較出大小後就可以構造紅黑樹了，最終構造出的紅黑樹如下：

橙色的箭頭表示 TreeNode 的 next 引用。由於空間有限，prev 引用未畫出。可以看出，鏈表轉成紅黑樹後，原鏈表的順序仍然會被引用仍被保留了（紅黑樹的根節點會被移動到鏈表的第一位），我們仍然可以按遍歷鏈表的方式去遍歷上面的紅黑樹。這樣的結構為後面紅黑樹的切分以及紅黑樹轉成鏈表做好了鋪墊，我們繼續往下分析。

紅黑樹拆分

擴容後，普通節點需要重新映射，紅黑樹節點也不例外。按照一般的思路，我們可以先把紅黑樹轉成鏈表，之後再重新映射鏈表即可。這種處理方式是大家比較容易想到的，但這樣做會損失一定的效率。不同於上面的處理方式，HashMap 實現的思路則是上好佳（上好佳請把廣告費打給我）。如上節所說，在將普通鏈表轉成紅黑樹時，HashMap 通過兩個額外的引用 next 和 prev 保留了原鏈表的節點順序。這樣再對紅黑樹進行重新映射時，完全可以按照映射鏈表的方式進行。這樣就避免了將紅黑樹轉成鏈表後再進行映射，無形中提高了效率。

以上就是紅黑樹拆分的邏輯，下面看一下具體實現吧：

// 紅黑樹轉鏈表閾值
static final int UNTREEIFY_THRESHOLD = 6;
final void split(HashMap map, Node[] tab, int index, int bit) {
 TreeNode b = this;
 // Relink into lo and hi lists, preserving order
 TreeNode loHead = null, loTail = null;
 TreeNode hiHead = null, hiTail = null;
 int lc = 0, hc = 0;
 /* 
 * 紅黑樹節點仍然保留了 next 引用，故仍可以按鏈表方式遍歷紅黑樹。
 * 下面的循環是對紅黑樹節點進行分組，與上面類似
 */
 for (TreeNode e = b, next; e != null; e = next) {
 next = (TreeNode)e.next;
 e.next = null;
 if ((e.hash & bit) == 0) {
 if ((e.prev = loTail) == null)
 loHead = e;
 else
 loTail.next = e;
 loTail = e;
 ++lc;
 }
 else {
 if ((e.prev = hiTail) == null)
 hiHead = e;
 else
 hiTail.next = e;
 hiTail = e;
 ++hc;
 }
 }
 if (loHead != null) {
 // 如果 loHead 不為空，且鏈表長度小於等於 6，則將紅黑樹轉成鏈表 

 if (lc <= UNTREEIFY_THRESHOLD)
 tab[index] = loHead.untreeify(map);
 else {
 tab[index] = loHead;
 /* 
 * hiHead == null 時，表明擴容後，
 * 所有節點仍在原位置，樹結構不變，無需重新樹化
 */
 if (hiHead != null) 
 loHead.treeify(tab);
 }
 }
 // 與上面類似
 if (hiHead != null) {
 if (hc <= UNTREEIFY_THRESHOLD)
 tab[index + bit] = hiHead.untreeify(map);
 else {
 tab[index + bit] = hiHead;
 if (loHead != null)
 hiHead.treeify(tab);
 }
 }
}

從源碼上可以看得出，重新映射紅黑樹的邏輯和重新映射鏈表的邏輯基本一致。不同的地方在於，重新映射後，會將紅黑樹拆分成兩條由 TreeNode 組成的鏈表。如果鏈表長度小於 UNTREEIFY_THRESHOLD，則將鏈表轉換成普通鏈表。否則根據條件重新將 TreeNode 鏈表樹化。舉個例子說明一下，假設擴容後，重新映射上圖的紅黑樹，映射結果如下：

紅黑樹鏈化

前面說過，紅黑樹中仍然保留了原鏈表節點順序。有了這個前提，再將紅黑樹轉成鏈表就簡單多了，僅需將 TreeNode 鏈表轉成 Node 類型的鏈表即可。相關代碼如下：

final Node untreeify(HashMap map) {
 Node hd = null, tl = null;
 // 遍歷 TreeNode 鏈表，並用 Node 替換
 for (Node 
 q = this; q != null; q = q.next) {
 // 替換節點類型
 Node p = map.replacementNode(q, null);
 if (tl == null)
 hd = p;
 else
 tl.next = p;
 tl = p;
 }
 return hd;
}
Node replacementNode(Node p, Node next) {
 return new Node<>(p.hash, p.key, p.value, next);
}

上面的代碼並不複雜，不難理解，這裡就不多說了。到此擴容相關內容就說完了，不知道大家理解沒。

刪除

如果大家堅持看完了前面的內容，到本節就可以輕鬆一下。當然，前提是不去看紅黑樹的刪除操作。不過紅黑樹並非本文講解重點，本節中也不會介紹紅黑樹相關內容，所以大家不用擔心。

HashMap 的刪除操作並不複雜，僅需三個步驟即可完成。第一步是定位桶位置，第二步遍歷鏈表並找到鍵值相等的節點，第三步刪除節點。相關源碼如下：

public V remove(Object key) {
 Node e;
 return (e = removeNode(hash(key), key, null, false, true)) == null ?
 null : e.value;
}
final Node removeNode(int hash, Object key, Object value,
 boolean matchValue, boolean movable) {
 Node[] tab; Node p; int n, index;
 if ((tab = table) != null && (n = tab.length) > 0 &&
 // 1. 定位桶位置
 (p = tab[index = (n - 1) & hash]) != null) {
 Node node = null, e; K k; V v;
 // 如果鍵的值與鏈表第一個節點相等，則將 node 指向該節點
 if (p.hash == hash &&
 ((k = p.key) == key || (key != null && key.equals(k))))
 node = p;
 else if ((e = p.next) != null) { 
 // 如果是 TreeNode 類型，調用紅黑樹的查找邏輯定位待刪除節點
 if (p instanceof TreeNode)
 node = ((TreeNode)p).getTreeNode(hash, key);
 else {
 // 2. 遍歷鏈表，找到待刪除節點
 do {
 if (e.hash == hash &&
 ((k = e.key) == key ||
 (key != null && key.equals(k)))) {
 node = e;
 break;
 }
 p = e;
 } while ((e = e.next) != null);
 }
 }
 
 // 3. 刪除節點，並修復鏈表或紅黑樹
 if (node != null && (!matchValue || (v = node.value) == value || 

 (value != null && value.equals(v)))) {
 if (node instanceof TreeNode)
 ((TreeNode)node).removeTreeNode(this, tab, movable);
 else if (node == p)
 tab[index] = node.next;
 else
 p.next = node.next;
 ++modCount;
 --size;
 afterNodeRemoval(node);
 return node;
 }
 }
 return null;
}

刪除操作本身並不複雜，有了前面的基礎，理解起來也就不難了，這裡就不多說了。

其他細節

前面的內容分析了 HashMap 的常用操作及相關的源碼，本節內容再補充一點其他方面的東西。

被 transient 所修飾 table 變量

如果大家細心閱讀 HashMap 的源碼，會發現桶數組 table 被申明為 transient。transient 表示易變的意思，在 Java 中，被該關鍵字修飾的變量不會被默認的序列化機制序列化。我們再回到源碼中，考慮一個問題：桶數組 table 是 HashMap 底層重要的數據結構，不序列化的話，別人還怎麼還原呢？

這裡簡單說明一下吧，HashMap 並沒有使用默認的序列化機制，而是通過實現readObject/writeObject兩個方法自定義了序列化的內容。這樣做是有原因的，試問一句，HashMap 中存儲的內容是什麼？不用說，大家也知道是鍵值對。所以只要我們把鍵值對序列化了，我們就可以根據鍵值對數據重建 HashMap。有的朋友可能會想，序列化 table 不是可以一步到位，後面直接還原不就行了嗎？這樣一想，倒也是合理。但序列化 talbe 存在著兩個問題：

• 1.table 多數情況下是無法被存滿的，序列化未使用的部分，浪費空間
• 2.同一個鍵值對在不同 JVM 下，所處的桶位置可能是不同的，在不同的 JVM 下反序列化 table 可能會發生錯誤。

以上兩個問題中，第一個問題比較好理解，第二個問題解釋一下。HashMap 的get/put/remove等方法第一步就是根據 hash 找到鍵所在的桶位置，但如果鍵沒有覆寫 hashCode 方法，計算 hash 時最終調用 Object 中的 hashCode 方法。但 Object 中的 hashCode 方法是 native 型的，不同的 JVM 下，可能會有不同的實現，產生的 hash 可能也是不一樣的。也就是說同一個鍵在不同平臺下可能會產生不同的 hash，此時再對在同一個 table 繼續操作，就會出現問題。

綜上所述，大家應該能明白 HashMap 不序列化 table 的原因了。

總結

本章對 HashMap 常見操作相關代碼進行了詳細分析，並在最後補充了一些其他細節。在本章中，插入操作一節的內容說的最多，主要是因為插入操作涉及的點特別多，一環扣一環。包含但不限於“table 初始化、擴容、樹化”等，總體來說，插入操作分析起來難度還是很大的。好在，最後分析完了。

本章篇幅雖比較大，但仍未把 HashMap 所有的點都分析到。比如，紅黑樹的增刪查等操作。當然，我個人看來，以上的分析已經夠了。畢竟大家是類庫的使用者而不是設計者，沒必要去弄懂每個細節。所以如果某些細節實在看不懂的話就跳過吧，對我們開發來說，知道 HashMap 大致原理即可。

好了，本章到此結束。

寫在最後

寫到這裡終於可以鬆一口氣了，這篇文章前前後後花了我一週多的時間。在我寫這篇文章之前，對 HashMap 認識僅限於原理層面，並未深入瞭解。一開始，我覺得關於 HashMap 沒什麼好寫的，畢竟大家對 HashMap 多少都有一定的瞭解。但等我深入閱讀 HashMap 源碼後，發現之前的認知是錯的。不是沒什麼可寫的，而是可寫的點太多了，不知道怎麼寫了。JDK 1.8 版本的 HashMap 實現上比之前版本要複雜的多，想弄懂眾多的細節難度還是不小的。僅自己弄懂還不夠，還要寫出來，難度就更大了，本篇文章基本上是在邊讀源碼邊寫的狀態下完成的。由於時間和能力有限，加之文章篇幅比較大，很難保證不出錯分析過程及配圖不出錯。如果有錯誤，希望大家指出來，我會及時修改，這裡先謝謝大家。

好了，本文就到這裡了，謝謝大家的閱讀！