參考
占小狼 ConcurrentHashMap 1.8擴(kuò)容分析
莫那一魯?shù)? ConcurrentHashMap#transfer() 擴(kuò)容逐行分析
思路比細(xì)節(jié)重要
一點(diǎn)思考
1.多核CPU才算真正意義上的并發(fā)坚弱，也就是同一時(shí)刻同時(shí)運(yùn)行相同的任務(wù)
- 每個(gè)線程都是在自己的工作內(nèi)存中操作新建立的數(shù)組上忍，他們是怎么協(xié)同工作的。
nextTab即新數(shù)組，第一個(gè)線程進(jìn)來(lái)的時(shí)候肯定是null蚕钦，然后創(chuàng)建一個(gè)大小為原數(shù)組兩倍的數(shù)組榨崩，再把值賦給nextTable削解，nextTable是volatile類(lèi)型的把夸，其他線程馬上可以取到最新值。 看了下transfer方法的調(diào)用入口锋华，nextTab這個(gè)參數(shù)要么是傳null值嗡官，要么是傳nextTable值所以后面線程進(jìn)來(lái)的時(shí)候nextTab值肯定是成員變量nextTable，也就是所有線程都是操作同一個(gè)數(shù)組毯焕，根據(jù)算法衍腥，每個(gè)CPU（線程）處理的桶的區(qū)間都不一樣，只是在不同的區(qū)間而已
擴(kuò)容時(shí)機(jī)
當(dāng)往hashMap中成功插入一個(gè)key/value節(jié)點(diǎn)時(shí)，有可能觸發(fā)擴(kuò)容動(dòng)作：
1婆咸、如果新增節(jié)點(diǎn)之后坊罢，所在鏈表的元素個(gè)數(shù)達(dá)到了閾值8，則會(huì)調(diào)用treeifyBin方法把鏈表轉(zhuǎn)換成紅黑樹(shù)擅耽，不過(guò)在結(jié)構(gòu)轉(zhuǎn)換之前，會(huì)對(duì)數(shù)組長(zhǎng)度進(jìn)行判斷物遇，
大體流程
1.通過(guò)計(jì)算 CPU 核心數(shù)和 Map 數(shù)組的長(zhǎng)度得到每個(gè)線程（CPU）要幫助處理多少個(gè)桶乖仇，并且這里每個(gè)線程處理都是平均的。默認(rèn)每個(gè)線程處理 16 個(gè)桶询兴。因此乃沙，如果長(zhǎng)度是 16 的時(shí)候，擴(kuò)容的時(shí)候只會(huì)有一個(gè)線程擴(kuò)容诗舰。
2.初始化臨時(shí)變量 nextTable警儒。將其在原有基礎(chǔ)上擴(kuò)容兩倍。
3.死循環(huán)開(kāi)始轉(zhuǎn)移眶根。多線程并發(fā)轉(zhuǎn)移就是在這個(gè)死循環(huán)中蜀铲，根據(jù)一個(gè) finishing 變量來(lái)判斷，該變量為 true 表示擴(kuò)容結(jié)束属百，否則繼續(xù)擴(kuò)容记劝。
3.1 進(jìn)入一個(gè) while 循環(huán)，分配數(shù)組中一個(gè)桶的區(qū)間給線程族扰，默認(rèn)是 16. 從大到小進(jìn)行分配厌丑。當(dāng)拿到分配值后，進(jìn)行 i-- 遞減渔呵。這個(gè) i 就是數(shù)組下標(biāo)怒竿。（其中有一個(gè) bound 參數(shù)，這個(gè)參數(shù)指的是該線程此次可以處理的區(qū)間的最小下標(biāo)扩氢，超過(guò)這個(gè)下標(biāo)耕驰，就需要重新領(lǐng)取區(qū)間或者結(jié)束擴(kuò)容，還有一個(gè) advance 參數(shù)录豺，該參數(shù)指的是是否繼續(xù)遞減轉(zhuǎn)移下一個(gè)桶耍属，如果為 true，表示可以繼續(xù)向后推進(jìn)巩检，反之厚骗，說(shuō)明還沒(méi)有處理好當(dāng)前桶，不能推進(jìn))
3.2 出 while 循環(huán)兢哭，進(jìn) if 判斷领舰，判斷擴(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)變量）。然后檢查所有的桶因苹，防止遺漏苟耻。
3.3 如果沒(méi)有完成任務(wù)，且 i 對(duì)應(yīng)的槽位是空扶檐，嘗試 CAS 插入占位符梁呈，讓 putVal 方法的線程感知。
3.4 如果 i 對(duì)應(yīng)的槽位不是空蘸秘，且有了占位符官卡，那么該線程跳過(guò)這個(gè)槽位，處理下一個(gè)槽位醋虏。
3.5 如果以上都是不是寻咒，說(shuō)明這個(gè)槽位有一個(gè)實(shí)際的值。開(kāi)始同步處理這個(gè)桶颈嚼。
3.6 到這里毛秘，都還沒(méi)有對(duì)桶內(nèi)數(shù)據(jù)進(jìn)行轉(zhuǎn)移，只是計(jì)算了下標(biāo)和處理區(qū)間阻课，然后一些完成狀態(tài)判斷叫挟。同時(shí)，如果對(duì)應(yīng)下標(biāo)內(nèi)沒(méi)有數(shù)據(jù)或已經(jīng)被占位了限煞，就跳過(guò)了抹恳。
處理每個(gè)桶的行為都是同步的。防止 putVal 的時(shí)候向鏈表插入數(shù)據(jù)署驻。
4.1 如果這個(gè)桶是鏈表奋献，那么就將這個(gè)鏈表根據(jù) length 取于拆成兩份健霹，取于結(jié)果是 0 的放在新表的低位，取于結(jié)果是 1 放在新表的高位瓶蚂。
4.2 如果這個(gè)桶是紅黑數(shù)糖埋，那么也拆成 2 份，方式和鏈表的方式一樣窃这，然后瞳别，判斷拆分過(guò)的樹(shù)的節(jié)點(diǎn)數(shù)量，如果數(shù)量小于等于 6杭攻，改造成鏈表祟敛。反之，繼續(xù)使用紅黑樹(shù)結(jié)構(gòu)朴上。
4.3 到這里，就完成了一個(gè)桶從舊表轉(zhuǎn)移到新表的過(guò)程卒煞。
好痪宰，以上，就是 transfer 方法的總體邏輯畔裕。還是挺復(fù)雜的衣撬。再進(jìn)行精簡(jiǎn)，分成 3 步驟：
計(jì)算每個(gè)線程可以處理的桶區(qū)間扮饶。默認(rèn) 16.
初始化臨時(shí)變量 nextTable具练，擴(kuò)容 2 倍。
死循環(huán)甜无，計(jì)算下標(biāo)扛点。完成總體判斷。
1 如果桶內(nèi)有數(shù)據(jù)岂丘，同步轉(zhuǎn)移數(shù)據(jù)陵究。通常會(huì)像鏈表拆成 2 份。
大體就是上的的 3 個(gè)步驟奥帘。
private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
int n = tab.length, stride;
// 將 length / 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 細(xì)分范圍 stridea：TODO
// 新的 table 尚未初始化
if (nextTab == null) { // initiating
try {
// 擴(kuò)容 2 倍
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
// 更新
nextTab = nt;
} catch (Throwable ex) { // try to cope with OOME
// 擴(kuò)容失敗秸苗， sizeCtl 使用 int 最大值。
sizeCtl = Integer.MAX_VALUE;
return;// 結(jié)束
}
// 更新成員變量
nextTable = nextTab;
// 更新轉(zhuǎn)移下標(biāo)运褪，就是 老的 tab 的 length
transferIndex = n;
}
// 新 tab 的 length
int nextn = nextTab.length;
// 創(chuàng)建一個(gè) fwd 節(jié)點(diǎn)难述，用于占位萤晴。當(dāng)別的線程發(fā)現(xiàn)這個(gè)槽位中是 fwd 類(lèi)型的節(jié)點(diǎn)，則跳過(guò)這個(gè)節(jié)點(diǎn)胁后。
ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
// 首次推進(jìn)為 true店读，如果等于 true，說(shuō)明需要再次推進(jìn)一個(gè)下標(biāo)（i--）攀芯，反之屯断，如果是 false，那么就不能推進(jìn)下標(biāo)侣诺，需要將當(dāng)前的下標(biāo)處理完畢才能繼續(xù)推進(jìn)
boolean advance = true;
// 完成狀態(tài)殖演，如果是 true，就結(jié)束此方法年鸳。
boolean finishing = false; // to ensure sweep before committing nextTab
// 死循環(huán),i 表示下標(biāo)趴久，bound 表示當(dāng)前線程可以處理的當(dāng)前桶區(qū)間最小下標(biāo)
for (int i = 0, bound = 0;;) {
Node<K,V> f; int fh;
// 如果當(dāng)前線程可以向后推進(jìn)；這個(gè)循環(huán)就是控制 i 遞減搔确。同時(shí)彼棍，每個(gè)線程都會(huì)進(jìn)入這里取得自己需要轉(zhuǎn)移的桶的區(qū)間
while (advance) {
int nextIndex, nextBound;
// 對(duì) i 減一，判斷是否大于等于 bound （正常情況下膳算，如果大于 bound 不成立座硕，說(shuō)明該線程上次領(lǐng)取的任務(wù)已經(jīng)完成了。那么涕蜂，需要在下面繼續(xù)領(lǐng)取任務(wù)）
// 如果對(duì) i 減一大于等于 bound（還需要繼續(xù)做任務(wù)）华匾，或者完成了，修改推進(jìn)狀態(tài)為 false机隙，不能推進(jìn)了蜘拉。任務(wù)成功后修改推進(jìn)狀態(tài)為 true。
// 通常有鹿，第一次進(jìn)入循環(huán)诸尽，i-- 這個(gè)判斷會(huì)無(wú)法通過(guò)，從而走下面的 nextIndex 賦值操作（獲取最新的轉(zhuǎn)移下標(biāo)）印颤。其余情況都是：如果可以推進(jìn)您机，將 i 減一，然后修改成不可推進(jìn)年局。如果 i 對(duì)應(yīng)的桶處理成功了际看，改成可以推進(jìn)。
if (--i >= bound || finishing)
advance = false;// 這里設(shè)置 false矢否，是為了防止在沒(méi)有成功處理一個(gè)桶的情況下卻進(jìn)行了推進(jìn)
// 這里的目的是：1. 當(dāng)一個(gè)線程進(jìn)入時(shí)仲闽，會(huì)選取最新的轉(zhuǎn)移下標(biāo)。2. 當(dāng)一個(gè)線程處理完自己的區(qū)間時(shí)僵朗，如果還有剩余區(qū)間的沒(méi)有別的線程處理赖欣。再次獲取區(qū)間屑彻。
else if ((nextIndex = transferIndex) <= 0) {
// 如果小于等于0，說(shuō)明沒(méi)有區(qū)間了 顶吮，i 改成 -1社牲，推進(jìn)狀態(tài)變成 false，不再推進(jìn)悴了，表示，擴(kuò)容結(jié)束了熟空，當(dāng)前線程可以退出了
// 這個(gè) -1 會(huì)在下面的 if 塊里判斷，從而進(jìn)入完成狀態(tài)判斷
i = -1;
advance = false;// 這里設(shè)置 false，是為了防止在沒(méi)有成功處理一個(gè)桶的情況下卻進(jìn)行了推進(jìn)
}// CAS 修改 transferIndex录淡，即 length - 區(qū)間值刨裆，留下剩余的區(qū)間值供后面的線程使用
else if (U.compareAndSwapInt
(this, TRANSFERINDEX, nextIndex,
nextBound = (nextIndex > stride ?
nextIndex - stride : 0))) {
bound = nextBound;// 這個(gè)值就是當(dāng)前線程可以處理的最小當(dāng)前區(qū)間最小下標(biāo)
i = nextIndex - 1; // 初次對(duì)i 賦值，這個(gè)就是當(dāng)前線程可以處理的當(dāng)前區(qū)間的最大下標(biāo)
advance = false; // 這里設(shè)置 false，是為了防止在沒(méi)有成功處理一個(gè)桶的情況下卻進(jìn)行了推進(jìn)，這樣對(duì)導(dǎo)致漏掉某個(gè)桶压怠。下面的 if (tabAt(tab, i) == f) 判斷會(huì)出現(xiàn)這樣的情況。
}
}// 如果 i 小于0 （不在 tab 下標(biāo)內(nèi)雇盖，按照上面的判斷娃闲，領(lǐng)取最后一段區(qū)間的線程擴(kuò)容結(jié)束）
// 如果 i >= tab.length(不知道為什么這么判斷)
// 如果 i + tab.length >= nextTable.length （不知道為什么這么判斷）
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é)束方法。
}// 如果沒(méi)完成
if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {// 嘗試將 sc -1. 表示這個(gè)線程結(jié)束幫助擴(kuò)容了，將 sc 的低 16 位減一。
if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)// 如果 sc - 2 不等于標(biāo)識(shí)符左移 16 位。如果他們相等了瓦堵，說(shuō)明沒(méi)有線程在幫助他們擴(kuò)容了陷揪。也就是說(shuō)，擴(kuò)容結(jié)束了。
return;// 不相等劲藐，說(shuō)明沒(méi)結(jié)束缝龄，當(dāng)前線程結(jié)束方法。
finishing = advance = true;// 如果相等嗅战，擴(kuò)容結(jié)束了脚曾，更新 finising 變量
i = n; // 再次循環(huán)檢查一下整張表
}
}
else if ((f = tabAt(tab, i)) == null) // 獲取老 tab i 下標(biāo)位置的變量旨椒，如果是 null涣仿，就使用 fwd 占位愉镰。
advance = casTabAt(tab, i, null, fwd);// 如果成功寫(xiě)入 fwd 占位，再次推進(jìn)一個(gè)下標(biāo)
else if ((fh = f.hash) == MOVED)// 如果不是 null 且 hash 值是 MOVED钧汹。
advance = true; // already processed // 說(shuō)明別的線程已經(jīng)處理過(guò)了丈探，再次推進(jìn)一個(gè)下標(biāo)
else {// 到這里，說(shuō)明這個(gè)位置有實(shí)際值了拔莱，且不是占位符碗降。對(duì)這個(gè)節(jié)點(diǎn)上鎖隘竭。為什么上鎖，防止 putVal 的時(shí)候向鏈表插入數(shù)據(jù)
synchronized (f) {
// 判斷 i 下標(biāo)處的桶節(jié)點(diǎn)是否和 f 相同
if (tabAt(tab, i) == f) {
Node<K,V> ln, hn;// low, height 高位桶讼渊，低位桶
// 如果 f 的 hash 值大于 0 动看。TreeBin 的 hash 是 -2
if (fh >= 0) {
// 對(duì)老長(zhǎng)度進(jìn)行與運(yùn)算（第一個(gè)操作數(shù)的的第n位于第二個(gè)操作數(shù)的第n位如果都是1，那么結(jié)果的第n為也為1爪幻，否則為0）
// 由于 Map 的長(zhǎng)度都是 2 的次方（000001000 這類(lèi)的數(shù)字）菱皆，那么取于 length 只有 2 種結(jié)果，一種是 0挨稿，一種是1
// 如果是結(jié)果是0 仇轻，Doug Lea 將其放在低位，反之放在高位奶甘，目的是將鏈表重新 hash拯田，放到對(duì)應(yīng)的位置上，讓新的取于算法能夠擊中他甩十。
int runBit = fh & n;
Node<K,V> lastRun = f; // 尾節(jié)點(diǎn)船庇，且和頭節(jié)點(diǎn)的 hash 值取于不相等
// 遍歷這個(gè)桶
for (Node<K,V> p = f.next; p != null; p = p.next) {
// 取于桶中每個(gè)節(jié)點(diǎn)的 hash 值
int b = p.hash & n;
// 如果節(jié)點(diǎn)的 hash 值和首節(jié)點(diǎn)的 hash 值取于結(jié)果不同
if (b != runBit) {
runBit = b; // 更新 runBit，用于下面判斷 lastRun 該賦值給 ln 還是 hn侣监。
lastRun = p; // 這個(gè) lastRun 保證后面的節(jié)點(diǎn)與自己的取于值相同鸭轮，避免后面沒(méi)有必要的循環(huán)
}
}
if (runBit == 0) {// 如果最后更新的 runBit 是 0 ，設(shè)置低位節(jié)點(diǎn)
ln = lastRun;
hn = null;
}
else {
hn = lastRun; // 如果最后更新的 runBit 是 1橄霉， 設(shè)置高位節(jié)點(diǎn)
ln = null;
}// 再次循環(huán)窃爷，生成兩個(gè)鏈表，lastRun 作為停止條件姓蜂，這樣就是避免無(wú)謂的循環(huán)（lastRun 后面都是相同的取于結(jié)果）
for (Node<K,V> p = f; p != lastRun; p = p.next) {
int ph = p.hash; K pk = p.key; V pv = p.val;
// 如果與運(yùn)算結(jié)果是 0按厘，那么就還在低位
if ((ph & n) == 0) // 如果是0 ，那么創(chuàng)建低位節(jié)點(diǎn)
ln = new Node<K,V>(ph, pk, pv, ln);
else // 1 則創(chuàng)建高位
hn = new Node<K,V>(ph, pk, pv, hn);
}
// 其實(shí)這里類(lèi)似 hashMap
// 設(shè)置低位鏈表放在新鏈表的 i
setTabAt(nextTab, i, ln);
// 設(shè)置高位鏈表钱慢，在原有長(zhǎng)度上加 n
setTabAt(nextTab, i + n, hn);
// 將舊的鏈表設(shè)置成占位符
setTabAt(tab, i, fwd);
// 繼續(xù)向后推進(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;
// 遍歷
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);
// 和鏈表相同的判斷逮京，與運(yùn)算 == 0 的放在低位
if ((h & n) == 0) {
if ((p.prev = loTail) == null)
lo = p;
else
loTail.next = p;
loTail = p;
++lc;
} // 不是 0 的放在高位
else {
if ((p.prev = hiTail) == null)
hi = p;
else
hiTail.next = p;
hiTail = p;
++hc;
}
}
// 如果樹(shù)的節(jié)點(diǎn)數(shù)小于等于 6，那么轉(zhuǎn)成鏈表束莫，反之懒棉，創(chuàng)建一個(gè)新的樹(shù)
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;
// 低位樹(shù)
setTabAt(nextTab, i, ln);
// 高位數(shù)
setTabAt(nextTab, i + n, hn);
// 舊的設(shè)置成占位符
setTabAt(tab, i, fwd);
// 繼續(xù)向后推進(jìn)
advance = true;
}
}
}
}
}
}
