ConcurrentHashMap在做鏈表遷移時，會用高低位來實現，這里有兩個問題要分析一下

1. 如何實現高低位鏈表的區分

假如我們有這樣一個隊列

第14個槽位插入新節點之后，鏈表元素個數已經達到了8，且數組長度為16，優先通過擴容來緩解鏈表過長的問題，擴容這塊的圖解稍后再分析，先分析高低位擴容的原理

假如當前線程正在處理槽位為14的節點，它是一個鏈表結構，在代碼中，首先定義兩個變量節點ln和hn，實際就是lowNode和HighNode，分別保存hash值的第x位為0和不等于0的節點

通過fn&n可以把這個鏈表中的元素分為兩類，A類是hash值的第X位為0，B類是hash值的第x位為不等于0（至于為什么要這么區分，稍后分析），并且通過lastRun記錄最后要處理的節點。最終要達到的目的是，A類的鏈表保持位置不動，B類的鏈表為14+16(擴容增加的長度)=30

我們把14槽位的鏈表單獨伶出來，我們用藍色表示?fn&n=0的節點，假如鏈表的分類是這樣

for (Node<K,V> p = f.next; p != null; p = p.next) { int b = p.hash & n;if (b != runBit) { runBit = b; lastRun = p; } }

?通過上面這段代碼遍歷，會記錄runBit以及lastRun，按照上面這個結構，那么runBit應該是藍色節點，lastRun應該是第6個節點

接著，再通過這段代碼進行遍歷，生成ln鏈以及hn鏈

for (Node<K,V> p = f; p != lastRun; p = p.next) { int ph = p.hash; K pk = p.key; V pv = p.val; if ((ph & n) == 0) ln = new Node<K,V>(ph, pk, pv, ln); else hn = new Node<K,V>(ph, pk, pv, hn); }

接著，通過CAS操作，把hn鏈放在i+n也就是14+16的位置，ln鏈保持原來的位置不動。并且設置當前節點為fwd，表示已經被當前線程遷移完了

setTabAt(nextTab, i, ln); setTabAt(nextTab, i + n, hn); setTabAt(tab, i, fwd);

遷移完成以后的數據分布如下

?

總結

以上是生活随笔為你收集整理的ConcurrentHashMap的源码分析-高低位原理分析的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。