在之前計(jì)數(shù)方法addCount()方法中，它有兩部分內(nèi)容疏尿，一個(gè)是計(jì)數(shù)另一個(gè)是擴(kuò)容瘟芝，在擴(kuò)容語(yǔ)句中有這樣一句：
transfer(tab, null);
這句話表示，當(dāng)?shù)谝粋€(gè)線程執(zhí)行擴(kuò)容操作的時(shí)候褥琐，會(huì)向transfer()傳入現(xiàn)在的表和一個(gè)空對(duì)象锌俱，好，我們一步步來(lái)看下這個(gè)方法的代碼敌呈。
第一部分代碼
private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
//stride為每個(gè)cpu所需要處理的桶個(gè)數(shù)
int n = tab.length, stride;
//將 n / 8 然后除以 CPU核心數(shù)贸宏。如果得到的結(jié)果小于 16，那么就使用 16磕洪。
//這里的目的是讓每個(gè) CPU 處理的桶一樣多吭练，避免出現(xiàn)轉(zhuǎn)移任務(wù)不均勻的現(xiàn)象，如果桶較少的話析显，默認(rèn)一個(gè) CPU（一個(gè)線程）處理 16 個(gè)桶
if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
stride = MIN_TRANSFER_STRIDE; // subdivide range
//新的 table 尚未初始化
if (nextTab == null) { // initiating
try {
@SuppressWarnings("unchecked")
//擴(kuò)容兩倍
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
nextTab = nt;
} catch (Throwable ex) { // try to cope with OOME
//如果擴(kuò)容出現(xiàn)錯(cuò)誤鲫咽，則sizeCtl賦值為int最大值返回
sizeCtl = Integer.MAX_VALUE;
return;
}
nextTable = nextTab;
//transferIndex代表的是舊數(shù)組的尾節(jié)點(diǎn)
transferIndex = n;
}
首先將舊表長(zhǎng)度賦值給n，然后另外申請(qǐng)了一個(gè)變量stride谷异，這個(gè)變量表示的是每個(gè)CPU所需要處理的桶的個(gè)數(shù)分尸，代碼中的第一個(gè)判斷語(yǔ)句可以看出，stride最小值為16歹嘹，也就是說(shuō)箩绍，當(dāng)桶的個(gè)數(shù)小于16的時(shí)候，默認(rèn)一個(gè)線程來(lái)處理所有的桶尺上。
第二條判斷語(yǔ)句是對(duì)nextTab的判斷材蛛，一開(kāi)始的時(shí)候圆到，我講到，在addCount()方法中為該參數(shù)傳入了一個(gè)Null值仰税，說(shuō)明table尚未初始化构资，需要進(jìn)行初始化，容量直接申請(qǐng)為舊表的兩倍陨簇，如果在擴(kuò)容中出現(xiàn)錯(cuò)誤，那么sizeCtl賦值為int最大值返回迹淌，然后需要注意的是transferIndex表示的遷移數(shù)據(jù)的下標(biāo)河绽，一開(kāi)始的下標(biāo)指向舊表的尾節(jié)點(diǎn)。
第二部分代碼
int nextn = nextTab.length;
//創(chuàng)建一個(gè)標(biāo)識(shí)類用于占位唉窃，當(dāng)其他線程掃描到這個(gè)類的時(shí)候會(huì)跳過(guò)
ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
//數(shù)組一層層推進(jìn)的標(biāo)識(shí)符
boolean advance = true;
//擴(kuò)容結(jié)束的標(biāo)識(shí)符
boolean finishing = false; // to ensure sweep before committing nextTab
for (int i = 0, bound = 0;;) {
Node<K,V> f; int fh;
//每個(gè)線程進(jìn)入這里耙饰，先獲取自己需要處理桶的區(qū)間，第一次進(jìn)入因?yàn)?-i纹份，會(huì)直接跳到else if中苟跪，對(duì)nextIndex進(jìn)行賦值操作
//這里設(shè)置了一個(gè)i = -1，
// 如果當(dāng)前線程可以向后推進(jìn)蔓涧；這個(gè)循環(huán)就是控制 i 遞減件已。同時(shí)，每個(gè)線程都會(huì)進(jìn)入這里取得自己需要轉(zhuǎn)移的桶的區(qū)間
while (advance) {
int nextIndex, nextBound;
if (--i >= bound || finishing)
//防止在沒(méi)有成功處理一個(gè)桶的情況下卻進(jìn)行了推進(jìn)
advance = false;
else if ((nextIndex = transferIndex) <= 0) {
i = -1;
//防止在沒(méi)有成功處理一個(gè)桶的情況下卻進(jìn)行了推進(jìn)
advance = false;
}
else if (U.compareAndSwapInt
(this, TRANSFERINDEX, nextIndex,
nextBound = (nextIndex > stride ?
nextIndex - stride : 0))) {
bound = nextBound;//線程負(fù)責(zé)桶區(qū)間當(dāng)前最小下標(biāo)
i = nextIndex - 1;//線程負(fù)責(zé)桶區(qū)間當(dāng)前最大下標(biāo)
advance = false;
}
}
if (i < 0 || i >= n || i + n >= nextn) {
int sc;
if (finishing) {//如果完成擴(kuò)容
nextTable = null;// 刪除成員變量
table = nextTab;// 更新 table
sizeCtl = (n << 1) - (n >>> 1); // 更新閾值
return;// 結(jié)束方法元暴。
}
if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
return;
finishing = advance = true;//擴(kuò)容結(jié)束
i = n; // 再次循環(huán)檢查一次表
}
}
//獲取老 tab i 下標(biāo)位置的變量篷扩，如果是 null，就使用 fwd 占位茉盏。
else if ((f = tabAt(tab, i)) == null)
//如果寫進(jìn)fwd鉴未，則推進(jìn)
advance = casTabAt(tab, i, null, fwd);
//如果當(dāng)前位置不是Null,且hash值為-1，說(shuō)明其他線程已經(jīng)處理過(guò)這個(gè)桶鸠姨，繼續(xù)推進(jìn)
else if ((fh = f.hash) == MOVED)
advance = true; // already processed
第二部分代碼主要是每個(gè)CPU負(fù)責(zé)的桶區(qū)間進(jìn)行規(guī)劃铜秆，然后進(jìn)行不同情況的判定工作，介紹下關(guān)鍵的幾個(gè)量
1讶迁、fwd:這個(gè)類是個(gè)標(biāo)識(shí)類连茧，用于指向新表用的，其他線程遇到這個(gè)類會(huì)主動(dòng)跳過(guò)這個(gè)類添瓷，因?yàn)檫@個(gè)類要么就是擴(kuò)容遷移正在進(jìn)行梅屉，要么就是已經(jīng)完成擴(kuò)容遷移，也就是這個(gè)類要保證線程安全鳞贷，再進(jìn)行操作坯汤。
2、advance:這個(gè)變量是用于提示代碼是否進(jìn)行推進(jìn)處理搀愧，也就是當(dāng)前桶處理完惰聂，處理下一個(gè)桶的標(biāo)識(shí)
3疆偿、finishing:這個(gè)變量用于提示擴(kuò)容是否結(jié)束用的
首先使用一個(gè)while(advance)循環(huán)出每個(gè)進(jìn)入該循環(huán)的線程所要負(fù)責(zé)的桶的區(qū)間，再判斷擴(kuò)容是否結(jié)束搓幌，如果擴(kuò)容結(jié)束杆故，清空臨死變量，更新 table 變量溉愁，更新庫(kù)容閾值处铛。如果沒(méi)完成，但已經(jīng)無(wú)法領(lǐng)取區(qū)間（沒(méi)了）拐揭，該線程退出該方法撤蟆，并將 sizeCtl 減一，表示擴(kuò)容的線程少一個(gè)了堂污。如果減完這個(gè)數(shù)以后家肯，sizeCtl 回歸了初始狀態(tài)，表示沒(méi)有線程再擴(kuò)容了盟猖，該方法所有的線程擴(kuò)容結(jié)束了讨衣。（這里主要是判斷擴(kuò)容任務(wù)是否結(jié)束，如果結(jié)束了就讓線程退出該方法式镐，并更新相關(guān)變量）反镇。然后檢查所有的桶，防止遺漏碟案。
接著判斷當(dāng)前位置是否為空愿险，為空則插入cas方法插入fwd，如果插入fwd成功繼續(xù)推進(jìn)
如果當(dāng)前位置不為空的情況下价说，hash值等于-1辆亏，表示當(dāng)前桶已經(jīng)完成擴(kuò)容和數(shù)據(jù)遷移操作
第三部分代碼
else {
//鎖住首節(jié)點(diǎn)
synchronized (f) {
//二次判斷地址偏移量所指向位置是否與f對(duì)象相等
if (tabAt(tab, i) == f) {
Node<K,V> ln, hn;
//fh>0為鏈表數(shù)據(jù)轉(zhuǎn)移
if (fh >= 0) {
//首節(jié)點(diǎn)的hash值
int runBit = fh & n;
Node<K,V> lastRun = f;//最后一個(gè)節(jié)點(diǎn)
//這個(gè)地方跟hashmap不同，hashmap是直接推進(jìn)到鏈表尾
//這個(gè)地方的處理在于想保留鏈表后所有hash值計(jì)算相同的點(diǎn)鳖目，這些點(diǎn)可以重復(fù)利用扮叨，不需要重新new
//所以下邊需要獲取哪個(gè)節(jié)點(diǎn)后的hash值全部相同
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==0，說(shuō)明低位重用
if (runBit == 0) {
ln = lastRun;
hn = null;
}
//高位重用
else {
hn = lastRun;
ln = null;
}
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)
//注意創(chuàng)建node節(jié)點(diǎn)的最后一個(gè)參數(shù)ln指代的是next
//也就是說(shuō)领迈，我們不再是從頭到尾節(jié)點(diǎn)彻磁，而是從為節(jié)點(diǎn)開(kāi)始向頭結(jié)點(diǎn)走
ln = new Node<K,V>(ph, pk, pv, ln);
else
hn = new Node<K,V>(ph, pk, pv, hn);
}
//將遍歷好的鏈表一放入i中
setTabAt(nextTab, i, ln);
//將遍歷好的鏈表二放入i+n中
setTabAt(nextTab, i + n, hn);
//將fwd占位放入舊表中
setTabAt(tab, i, fwd);
//向前推進(jìn)
advance = true;
}
//如果是紅黑樹(shù)
else if (f instanceof TreeBin) {
TreeBin<K,V> t = (TreeBin<K,V>)f;
TreeNode<K,V> lo = null, loTail = null;
TreeNode<K,V> hi = null, hiTail = null;
int lc = 0, hc = 0;
//遍歷，將鏈表轉(zhuǎn)成雙端鏈表
for (Node<K,V> e = t.first; e != null; e = e.next) {
int h = e.hash;
TreeNode<K,V> p = new TreeNode<K,V>
(h, e.key, e.val, null, null);
if ((h & n) == 0) {
if ((p.prev = loTail) == null)
lo = p;
else
loTail.next = p;
loTail = p;
++lc;
}
else {
if ((p.prev = hiTail) == null)
hi = p;
else
hiTail.next = p;
hiTail = p;
++hc;
}
}
//如果長(zhǎng)度小于等于6狸捅，則將紅黑樹(shù)轉(zhuǎn)換成鏈表
ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :
(hc != 0) ? new TreeBin<K,V>(lo) : t;
hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
(lc != 0) ? new TreeBin<K,V>(hi) : t;
setTabAt(nextTab, i, ln);
setTabAt(nextTab, i + n, hn);
setTabAt(tab, i, fwd);
advance = true;
}
}
}
}
}
}
第三部分代碼跟hashmap中的類似衷蜓，也是使用synchronized來(lái)鎖定頭結(jié)點(diǎn)，然后根據(jù)鏈表和紅黑樹(shù)分開(kāi)進(jìn)行判斷數(shù)據(jù)遷移尘喝，如果是鏈表磁浇，ConcurrentHashmap比hashmap多了一個(gè)步驟，使用runBit來(lái)記錄頭結(jié)點(diǎn)hash值朽褪，然后遍歷鏈表一個(gè)個(gè)跟runBit進(jìn)行比較置吓，runBit只有兩種可能无虚，一種是為0，另一種是為1衍锚，也就是說(shuō)友题，如果為0，則低位上可以有很多重用的節(jié)點(diǎn)戴质，如果為1則表示高位上有很多重用的節(jié)點(diǎn)度宦，用lastRun來(lái)記錄某個(gè)節(jié)點(diǎn)后runBit不變呢岗，也就是lastRun節(jié)點(diǎn)后的節(jié)點(diǎn)都是重用的彻桃，然后遍歷lastRun之前的節(jié)點(diǎn)慰安，這個(gè)地方也不同攻晒，hashmap是從頭通過(guò)node的next屬性進(jìn)行從頭往后添加節(jié)點(diǎn)，而ConcurrentHashmap是從尾開(kāi)始往前添加節(jié)點(diǎn)胰蝠，直到添加到首節(jié)點(diǎn)，然后通過(guò)setTabAt()方法添加到新表的桶中，最后在舊表放入一個(gè)fwd占位符行贪。
紅黑樹(shù)跟鏈表也差不多，分出兩個(gè)紅黑樹(shù)模闲，一個(gè)在高位一個(gè)在低位建瘫，分出來(lái)的紅黑樹(shù)再進(jìn)行長(zhǎng)度判斷，長(zhǎng)度小于等于6的會(huì)通過(guò)方法untreeify()轉(zhuǎn)換成鏈表結(jié)構(gòu)存儲(chǔ)尸折。
參考鏈接：
http://www.reibang.com/p/2829fe36a8dd
https://blog.csdn.net/u011392897/article/details/60479937
https://www.cnblogs.com/stateis0/p/9062095.html
