ConcurrentHashMap的擴容為了提高效率,是多線程并發的
每個線程控制一部分范圍節點的擴容(根據cpu與數組長度確定控制多大范圍)
有兩個核心參數
sizeCtl:標記擴容狀態 負數時代表正在擴容,存儲量參與擴容的線程數,正數代表出發擴容的閾值
transferIndex:表示當前等待遷移的舊表的最大索引(由高到低遷移 )若map數組長度為16則就該值的初時值是15
需要注意的是進行擴容的線程并不是Map自己創建的,而是抓的壯丁!誰觸發,誰就被抓來協助擴容。
既然是多線程并發,那就一定是每個線程負責一部分,怎么確定哪些線程負責那些部分,避免重復遷移呢?這就要用到transferIndex,
所有線程嘗試去獲取自己負責的部分時,都要嘗試cas修改這個值,注意每次的獲取是分塊的,有一個stide 每個線程至少是16個,即16個桶,cas修改transferIndex后就開始遷移元素。
元素的遷移過程中,線程會依次獲取自己負責范圍內的鎖桶,注意不是一口氣全拿,而是遷移一個拿一個,遷移完就釋放,確保其他線程可正常讀寫還沒有被遷移的桶。遷移完后的桶的頭結點會被標記成ForwardingNode,表示該桶已被遷移,此時若有線程讀取該桶的數據,則會到新表中取查詢。
遷移時也會根據高低位來判斷是否要遷移,將舊桶的鏈表拆分為兩個鏈表(低位鏈表和高位鏈表),分別放到新表的?
i
和?i + oldCapacity
位置。??紅黑樹遷移??:類似鏈表,但需檢查拆分后的節點數量,若小于?
UNTREEIFY_THRESHOLD
(默認 6),則退化為鏈表遷移完成前并不會真正斷開舊表對元素的引用,這樣對與正在遷移的桶,可以直接get其中的元素
最后完成擴容后會用nexttable 替換舊表
并修改sizeCtl會新容量的0.75倍
遷移過程中的put和get
get:若未被遷移直接讀,被遷移(發現頭結點是ForwardingNode,會跳轉到對應的新表節點)從新表中讀
put:會主動協助擴容,寫操作一定要獲取到桶鎖