深入分析 ConcurrentHashMap 1.8 的擴容實現-知識星球

（點選上方公眾號，可快速關註）

來源：佔小狼，

www.jianshu.com/p/f6730d5784ad

ConcurrentHashMap相關的文章寫了不少，有個遺留問題一直沒有分析，也被好多人請教過，被擱置在一旁，即如何在併發的情況下實現陣列的擴容。

什麼情況會觸發擴容

當往hashMap中成功插入一個key/value節點時，有可能觸發擴容動作：

1、如果新增節點之後，所在連結串列的元素個數達到了閾值 8，則會呼叫treeifyBin方法把連結串列轉換成紅黑樹，不過在結構轉換之前，會對陣列長度進行判斷，實現如下：

如果陣列長度n小於閾值MIN_TREEIFY_CAPACITY，預設是64，則會呼叫tryPresize方法把陣列長度擴大到原來的兩倍，並觸發transfer方法，重新調整節點的位置。

2、新增節點之後，會呼叫addCount方法記錄元素個數，並檢查是否需要進行擴容，當陣列元素個數達到閾值時，會觸發transfer方法，重新調整節點的位置。

transfer實現

transfer方法實現了在併發的情況下，高效的從原始組數往新陣列中移動元素，假設擴容之前節點的分佈如下，這裡區分藍色節點和紅色節點，是為了後續更好的分析：

在上圖中，第14個槽位插入新節點之後，連結串列元素個數已經達到了8，且陣列長度為16，優先透過擴容來緩解連結串列過長的問題，實現如下：

1、根據當前陣列長度n，新建一個兩倍長度的陣列nextTable；

2、初始化ForwardingNode節點，其中儲存了新陣列nextTable的取用，在處理完每個槽位的節點之後當做佔位節點，表示該槽位已經處理過了；

3、透過for自迴圈處理每個槽位中的連結串列元素，預設advace為真，透過CAS設定transferIndex屬性值，並初始化i和bound值，i指當前處理的槽位序號，bound指需要處理的槽位邊界，先處理槽位15的節點；

4、在當前假設條件下，槽位15中沒有節點，則透過CAS插入在第二步中初始化的ForwardingNode節點，用於告訴其它執行緒該槽位已經處理過了；

5、如果槽位15已經被執行緒A處理了，那麼執行緒B處理到這個節點時，取到該節點的hash值應該為MOVED，值為-1，則直接跳過，繼續處理下一個槽位14的節點；

6、處理槽位14的節點，是一個連結串列結構，先定義兩個變數節點ln和hn，按我的理解應該是lowNode和highNode，分別儲存hash值的第X位為0和1的節點，具體實現如下：

使用fn&n;可以快速把連結串列中的元素區分成兩類，A類是hash值的第X位為0，B類是hash值的第X位為1，並透過lastRun記錄最後需要處理的節點，A類和B類節點可以分散到新陣列的槽位14和30中，在原陣列的槽位14中，藍色節點第X為0，紅色節點第X為1，把連結串列拉平顯示如下：

ln鏈：和原來鏈表相比，順序已經不一樣了

hn鏈：

透過CAS把ln連結串列設定到新陣列的i位置，hn連結串列設定到i+n的位置；

7、如果該槽位是紅黑樹結構，則構造樹節點lo和hi，遍歷紅黑樹中的節點，同樣根據hash&n;演演算法，把節點分為兩類，分別插入到lo和hi為頭的連結串列中，根據lo和hi連結串列中的元素個數分別生成ln和hn節點，其中ln節點的生成邏輯如下：

（1）如果lo連結串列的元素個數小於等於UNTREEIFY_THRESHOLD，預設為6，則透過untreeify方法把樹節點連結串列轉化成普通節點連結串列；

（2）否則判斷hi連結串列中的元素個數是否等於0：如果等於0，表示lo連結串列中包含了所有原始節點，則設定原始紅黑樹給ln，否則根據lo連結串列重新構造紅黑樹。

最後，同樣的透過CAS把ln設定到新陣列的i位置，hn設定到i+n位置。

相關文章

看完本文有收穫？請轉發分享給更多人

關註「ImportNew」，提升Java技能

深入分析 ConcurrentHashMap 1.8 的擴容實現