歡迎光臨
每天分享高質量文章

深入分析 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,把連結串列拉平顯示如下:

  • 透過遍歷連結串列,記錄runBit和lastRun,分別為1和節點6,所以設定hn為節點6,ln為null;

  • 重新遍歷連結串列,以lastRun節點為終止條件,根據第X位的值分別構造ln連結串列和hn連結串列:

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位置。

相關文章

  1. 深入淺出ConcurrentHashMap(1.8)

    http://www.jianshu.com/p/c0642afe03e0

  2. 談談ConcurrentHashMap1.7和1.8的不同實現

    http://www.importnew.com/?p=23610

  3. ConcurrentHashMap的紅黑樹實現分析

    http://www.importnew.com/?p=23621

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

關註「ImportNew」,提升Java技能

贊(0)

分享創造快樂