摘要：一擴(kuò)容的基本思路中，最復(fù)雜的部分就是擴(kuò)容數(shù)據(jù)遷移，涉及多線程的合作和。單線程注意這兩種情況都是調(diào)用了方法，通過(guò)第二個(gè)入?yún)⑦M(jìn)行區(qū)分表示擴(kuò)容后的新數(shù)組，如果為，表示首次發(fā)起擴(kuò)容。第二種情況下，是通過(guò)和移位運(yùn)算來(lái)保證僅有一個(gè)線程能發(fā)起擴(kuò)容。
本文首發(fā)于一世流云專(zhuān)欄：https://segmentfault.com/blog...
通過(guò)上一篇文章——ConcurrentHashMap原理(1)，相信讀者對(duì)ConcurrentHashMap的基本原理有了一個(gè)初步認(rèn)識(shí)，但是上一篇中還有一個(gè)遺留問(wèn)題沒(méi)有討論到，那就是ConcurrentHashMap的擴(kuò)容和數(shù)據(jù)遷移。本文中，我們將會(huì)對(duì)這兩個(gè)問(wèn)題進(jìn)行討論。
一、擴(kuò)容的基本思路
JDK1.8中，ConcurrentHashMap最復(fù)雜的部分就是擴(kuò)容/數(shù)據(jù)遷移，涉及多線程的合作和rehash。我們先來(lái)考慮下一般情況下，如何對(duì)一個(gè)Hash表進(jìn)行擴(kuò)容。
擴(kuò)容思路
Hash表的擴(kuò)容，一般都包含兩個(gè)步驟：
①table數(shù)組的擴(kuò)容
table數(shù)組的擴(kuò)容，一般就是新建一個(gè)2倍大小的槽數(shù)組，這個(gè)過(guò)程通過(guò)由一個(gè)單線程完成，且不允許出現(xiàn)并發(fā)。
②數(shù)據(jù)遷移
所謂數(shù)據(jù)遷移，就是把舊table中的各個(gè)槽中的結(jié)點(diǎn)重新分配到新table中。比如，單線程情況下，可以遍歷原來(lái)的table，然后put到新table中。
這一過(guò)程通常涉及到槽中key的rehash，因?yàn)閗ey映射到桶的位置與table的大小有關(guān)，新table的大小變了，key映射的位置一般也會(huì)變化。
ConcurrentHashMap在處理rehash的時(shí)候，并不會(huì)重新計(jì)算每個(gè)key的hash值，而是利用了一種很巧妙的方法。我們?cè)谏弦黄f(shuō)過(guò)，ConcurrentHashMap內(nèi)部的table數(shù)組的大小必須為2的冪次，原因是讓key均勻分布，減少?zèng)_突，這只是其中一個(gè)原因。另一個(gè)原因就是：
當(dāng)table數(shù)組的大小為2的冪次時(shí)，通過(guò)key.hash & table.length-1這種方式計(jì)算出的索引i，當(dāng)table擴(kuò)容后（2倍），新的索引要么在原來(lái)的位置i，要么是i+n。
我們來(lái)看個(gè)例子：
上圖中：
擴(kuò)容前，table數(shù)組大小為16，key1和key2映射到同一個(gè)索引5；
擴(kuò)容后，table數(shù)組的大小變成 2*16=32 ，key1的索引不變，key2的索引變成 5+16=21。
而且還有一個(gè)特點(diǎn)，擴(kuò)容后key對(duì)應(yīng)的索引如果發(fā)生了變化，那么其變化后的索引最高位一定是1（見(jiàn)擴(kuò)容后key2的最高位）。
這種處理方式非常利于擴(kuò)容時(shí)多個(gè)線程同時(shí)進(jìn)行的數(shù)據(jù)遷移操作，因?yàn)榕ftable的各個(gè)桶中的結(jié)點(diǎn)遷移不會(huì)互相影響，所以就可以用“分治”的方式，將整個(gè)table數(shù)組劃分為很多部分，每一部分包含一定區(qū)間的桶，每個(gè)數(shù)據(jù)遷移線程處理各自區(qū)間中的結(jié)點(diǎn)，對(duì)多線程同時(shí)進(jìn)行數(shù)據(jù)遷移非常有利，后面我們會(huì)詳細(xì)介紹。
擴(kuò)容時(shí)機(jī)
我們?cè)賮?lái)看下，ConcurrentHashMap何時(shí)會(huì)發(fā)生擴(kuò)容。
在上篇文章中，我們提到過(guò)，當(dāng)往Map中插入結(jié)點(diǎn)時(shí)，如果鏈表的結(jié)點(diǎn)數(shù)目超過(guò)一定閾值，就會(huì)觸發(fā)鏈表 -> 紅黑樹(shù)的轉(zhuǎn)換：
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i); // 鏈表 -> 紅黑樹(shù) 轉(zhuǎn)換
現(xiàn)在，我們來(lái)分析下treeifyBin這個(gè)紅黑樹(shù)化的操作：
/**
* 嘗試進(jìn)行 鏈表 -> 紅黑樹(shù) 的轉(zhuǎn)換.
*/
private final void treeifyBin(Node[] tab, int index) {
Node b;
int n, sc;
if (tab != null) {
// CASE 1: table的容量 < MIN_TREEIFY_CAPACITY(64)時(shí)，直接進(jìn)行table擴(kuò)容，不進(jìn)行紅黑樹(shù)轉(zhuǎn)換
if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
tryPresize(n << 1);
// CASE 2: table的容量 ≥ MIN_TREEIFY_CAPACITY(64)時(shí)，進(jìn)行鏈表 -> 紅黑樹(shù)的轉(zhuǎn)換
else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
synchronized (b) {
if (tabAt(tab, index) == b) {
TreeNode hd = null, tl = null;
// 遍歷鏈表，建立紅黑樹(shù)
for (Node e = b; e != null; e = e.next) {
TreeNode p = new TreeNode(e.hash, e.key, e.val, null, null);
if ((p.prev = tl) == null)
hd = p;
else
tl.next = p;
tl = p;
}
// 以TreeBin類(lèi)型包裝，并鏈接到table[index]中
setTabAt(tab, index, new TreeBin(hd));
}
}
}
}
}
上述第一個(gè)分支中，還會(huì)再對(duì)table數(shù)組的長(zhǎng)度進(jìn)行一次判斷：
如果table長(zhǎng)度小于閾值MIN_TREEIFY_CAPACITY——默認(rèn)64，則會(huì)調(diào)用tryPresize方法把數(shù)組長(zhǎng)度擴(kuò)大到原來(lái)的兩倍。
從代碼也可以看到，鏈表 -> 紅黑樹(shù)這一轉(zhuǎn)換并不是一定會(huì)進(jìn)行的，table長(zhǎng)度較小時(shí)，CurrentHashMap會(huì)首先選擇擴(kuò)容，而非立即轉(zhuǎn)換成紅黑樹(shù)。
來(lái)看下tryPresize方法如何執(zhí)行擴(kuò)容：
/**
* 嘗試對(duì)table數(shù)組進(jìn)行擴(kuò)容.
*
* @param 待擴(kuò)容的大小
*/
private final void tryPresize(int size) {
// 視情況將size調(diào)整為2的冪次
int c = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY : tableSizeFor(size + (size >>> 1) + 1);
int sc;
while ((sc = sizeCtl) >= 0) {
Node[] tab = table;
int n;
//CASE 1: table還未初始化，則先進(jìn)行初始化
if (tab == null || (n = tab.length) == 0) {
n = (sc > c) ? sc : c;
if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
try {
if (table == tab) {
Node[] nt = (Node[]) new Node[n];
table = nt;
sc = n - (n >>> 2);
}
} finally {
sizeCtl = sc;
}
}
}
// CASE2: c <= sc說(shuō)明已經(jīng)被擴(kuò)容過(guò)了；n >= MAXIMUM_CAPACITY說(shuō)明table數(shù)組已達(dá)到最大容量
else if (c <= sc || n >= MAXIMUM_CAPACITY)
break;
// CASE3: 進(jìn)行table擴(kuò)容
else if (tab == table) {
int rs = resizeStamp(n); // 根據(jù)容量n生成一個(gè)隨機(jī)數(shù)，唯一標(biāo)識(shí)本次擴(kuò)容操作
if (sc < 0) { // sc < 0 表明此時(shí)有別的線程正在進(jìn)行擴(kuò)容
Node[] nt;
// 如果當(dāng)前線程無(wú)法協(xié)助進(jìn)行數(shù)據(jù)轉(zhuǎn)移, 則退出
if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
transferIndex <= 0)
break;
// 協(xié)助數(shù)據(jù)轉(zhuǎn)移, 把正在執(zhí)行transfer任務(wù)的線程數(shù)加1
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
transfer(tab, nt);
}
// sc置為負(fù)數(shù), 當(dāng)前線程自身成為第一個(gè)執(zhí)行transfer(數(shù)據(jù)轉(zhuǎn)移)的線程
// 這個(gè)CAS操作可以保證，僅有一個(gè)線程會(huì)執(zhí)行擴(kuò)容
else if (U.compareAndSwapInt(this, SIZECTL, sc, (rs << RESIZE_STAMP_SHIFT) + 2))
transfer(tab, null);
}
}
}
前兩個(gè)分支沒(méi)什么好說(shuō)的，看下注釋很容易理解，關(guān)鍵看第三個(gè)分支 —— CASE3：進(jìn)行table擴(kuò)容。
CASE3其實(shí)分為兩種情況：
已經(jīng)有其它線程正在執(zhí)行擴(kuò)容了，則當(dāng)前線程會(huì)嘗試協(xié)助“數(shù)據(jù)遷移”；（多線程并發(fā)）
沒(méi)有其它線程正在執(zhí)行擴(kuò)容，則當(dāng)前線程自身發(fā)起擴(kuò)容。（單線程）
注意：這兩種情況都是調(diào)用了transfer方法，通過(guò)第二個(gè)入?yún)extTab進(jìn)行區(qū)分（nextTab表示擴(kuò)容后的新table數(shù)組，如果為null，表示首次發(fā)起擴(kuò)容）。
第二種情況下，是通過(guò)CAS和移位運(yùn)算來(lái)保證僅有一個(gè)線程能發(fā)起擴(kuò)容。
二、擴(kuò)容的原理
我們來(lái)看下transfer方法，這個(gè)方法可以被多個(gè)線程同時(shí)調(diào)用，也是“數(shù)據(jù)遷移”的核心操作方法：
/**
* 數(shù)據(jù)轉(zhuǎn)移和擴(kuò)容.
* 每個(gè)調(diào)用tranfer的線程會(huì)對(duì)當(dāng)前舊table中[transferIndex-stride, transferIndex-1]位置的結(jié)點(diǎn)進(jìn)行遷移
*
* @param tab 舊table數(shù)組
* @param nextTab 新table數(shù)組
*/
private final void transfer(Node[] tab, Node[] nextTab) {
int n = tab.length, stride;
// stride可理解成“步長(zhǎng)”，即數(shù)據(jù)遷移時(shí)，每個(gè)線程要負(fù)責(zé)舊table中的多少個(gè)桶
if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
stride = MIN_TRANSFER_STRIDE;
if (nextTab == null) { // 首次擴(kuò)容
try {
// 創(chuàng)建新table數(shù)組
Node[] nt = (Node[]) new Node[n << 1];
nextTab = nt;
} catch (Throwable ex) { // 處理內(nèi)存溢出（OOME）的情況
sizeCtl = Integer.MAX_VALUE;
return;
}
nextTable = nextTab;
transferIndex = n; // [transferIndex-stride, transferIndex-1]表示當(dāng)前線程要進(jìn)行數(shù)據(jù)遷移的桶區(qū)間
}
int nextn = nextTab.length;
// ForwardingNode結(jié)點(diǎn)，當(dāng)舊table的某個(gè)桶中的所有結(jié)點(diǎn)都遷移完后，用該結(jié)點(diǎn)占據(jù)這個(gè)桶
ForwardingNode fwd = new ForwardingNode(nextTab);
// 標(biāo)識(shí)一個(gè)桶的遷移工作是否完成，advance == true 表示可以進(jìn)行下一個(gè)位置的遷移
boolean advance = true;
// 最后一個(gè)數(shù)據(jù)遷移的線程將該值置為true，并進(jìn)行本輪擴(kuò)容的收尾工作
boolean finishing = false;
// i標(biāo)識(shí)桶索引, bound標(biāo)識(shí)邊界
for (int i = 0, bound = 0; ; ) {
Node f;
int fh;
// 每一次自旋前的預(yù)處理，主要是定位本輪處理的桶區(qū)間
// 正常情況下，預(yù)處理完成后：i == transferIndex-1，bound == transferIndex-stride
while (advance) {
int nextIndex, nextBound;
if (--i >= bound || finishing)
advance = false;
else if ((nextIndex = transferIndex) <= 0) {
i = -1;
advance = false;
} else if (U.compareAndSwapInt(this, TRANSFERINDEX, nextIndex,
nextBound = (nextIndex > stride ? nextIndex - stride : 0))) {
bound = nextBound;
i = nextIndex - 1;
advance = false;
}
}
if (i < 0 || i >= n || i + n >= nextn) { // CASE1：當(dāng)前是處理最后一個(gè)tranfer任務(wù)的線程或出現(xiàn)擴(kuò)容沖突
int sc;
if (finishing) { // 所有桶遷移均已完成
nextTable = null;
table = nextTab;
sizeCtl = (n << 1) - (n >>> 1);
return;
}
// 擴(kuò)容線程數(shù)減1,表示當(dāng)前線程已完成自己的transfer任務(wù)
if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
// 判斷當(dāng)前線程是否是本輪擴(kuò)容中的最后一個(gè)線程，如果不是，則直接退出
if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
return;
finishing = advance = true;
/**
* 最后一個(gè)數(shù)據(jù)遷移線程要重新檢查一次舊table中的所有桶，看是否都被正確遷移到新table了：
* ①正常情況下，重新檢查時(shí)，舊table的所有桶都應(yīng)該是ForwardingNode;
* ②特殊情況下，比如擴(kuò)容沖突(多個(gè)線程申請(qǐng)到了同一個(gè)transfer任務(wù))，此時(shí)當(dāng)前線程領(lǐng)取的任務(wù)會(huì)作廢，那么最后檢查時(shí)，
* 還要處理因?yàn)樽鲝U而沒(méi)有被遷移的桶，把它們正確遷移到新table中
*/
i = n; // recheck before commit
}
} else if ((f = tabAt(tab, i)) == null) // CASE2：舊桶本身為null，不用遷移，直接嘗試放一個(gè)ForwardingNode
advance = casTabAt(tab, i, null, fwd);
else if ((fh = f.hash) == MOVED) // CASE3：該舊桶已經(jīng)遷移完成，直接跳過(guò)
advance = true;
else { // CASE4：該舊桶未遷移完成，進(jìn)行數(shù)據(jù)遷移
synchronized (f) {
if (tabAt(tab, i) == f) {
Node ln, hn;
if (fh >= 0) { // CASE4.1：桶的hash>0，說(shuō)明是鏈表遷移
/**
* 下面的過(guò)程會(huì)將舊桶中的鏈表分成兩部分：ln鏈和hn鏈
* ln鏈會(huì)插入到新table的槽i中，hn鏈會(huì)插入到新table的槽i+n中
*/
int runBit = fh & n; // 由于n是2的冪次，所以runBit要么是0，要么高位是1
Node lastRun = f; // lastRun指向最后一個(gè)相鄰runBit不同的結(jié)點(diǎn)
for (Node p = f.next; p != null; p = p.next) {
int b = p.hash & n;
if (b != runBit) {
runBit = b;
lastRun = p;
}
}
if (runBit == 0) {
ln = lastRun;
hn = null;
} else {
hn = lastRun;
ln = null;
}
// 以lastRun所指向的結(jié)點(diǎn)為分界，將鏈表拆成2個(gè)子鏈表ln、hn
for (Node 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(ph, pk, pv, ln);
else
hn = new Node(ph, pk, pv, hn);
}
setTabAt(nextTab, i, ln); // ln鏈表存入新桶的索引i位置
setTabAt(nextTab, i + n, hn); // hn鏈表存入新桶的索引i+n位置
setTabAt(tab, i, fwd); // 設(shè)置ForwardingNode占位
advance = true; // 表示當(dāng)前舊桶的結(jié)點(diǎn)已遷移完畢
}
else if (f instanceof TreeBin) { // CASE4.2：紅黑樹(shù)遷移
/**
* 下面的過(guò)程會(huì)先以鏈表方式遍歷，復(fù)制所有結(jié)點(diǎn)，然后根據(jù)高低位組裝成兩個(gè)鏈表；
* 然后看下是否需要進(jìn)行紅黑樹(shù)轉(zhuǎn)換，最后放到新table對(duì)應(yīng)的桶中
*/
TreeBin t = (TreeBin) f;
TreeNode lo = null, loTail = null;
TreeNode hi = null, hiTail = null;
int lc = 0, hc = 0;
for (Node e = t.first; e != null; e = e.next) {
int h = e.hash;
TreeNode p = new TreeNode
(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;
}
}
// 判斷是否需要進(jìn)行 紅黑樹(shù) <-> 鏈表 的轉(zhuǎn)換
ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :
(hc != 0) ? new TreeBin(lo) : t;
hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
(lc != 0) ? new TreeBin(hi) : t;
setTabAt(nextTab, i, ln);
setTabAt(nextTab, i + n, hn);
setTabAt(tab, i, fwd); // 設(shè)置ForwardingNode占位
advance = true; // 表示當(dāng)前舊桶的結(jié)點(diǎn)已遷移完畢
}
}
}
}
}
}
tranfer方法的開(kāi)頭，會(huì)計(jì)算出一個(gè)stride變量的值，這個(gè)stride其實(shí)就是每個(gè)線程處理的桶區(qū)間，也就是步長(zhǎng)：
// stride可理解成“步長(zhǎng)”，即數(shù)據(jù)遷移時(shí)，每個(gè)線程要負(fù)責(zé)舊table中的多少個(gè)桶
if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
stride = MIN_TRANSFER_STRIDE;
首次擴(kuò)容時(shí)，會(huì)將table數(shù)組變成原來(lái)的2倍：
if (nextTab == null) { // 首次擴(kuò)容
try {
// 創(chuàng)建新table數(shù)組
Node[] nt = (Node[]) new Node[n << 1];
nextTab = nt;
} catch (Throwable ex) { // 處理內(nèi)存溢出（OOME）的情況
sizeCtl = Integer.MAX_VALUE;
return;
}
nextTable = nextTab;
transferIndex = n; // [transferIndex-stride, transferIndex-1]表示當(dāng)前線程要進(jìn)行數(shù)據(jù)遷移的桶區(qū)間
}
注意上面的transferIndex變量，這是一個(gè)字段，table[transferIndex-stride, transferIndex-1]就是當(dāng)前線程要進(jìn)行數(shù)據(jù)遷移的桶區(qū)間：
/**
* 擴(kuò)容時(shí)需要用到的一個(gè)下標(biāo)變量.
*/
private transient volatile int transferIndex;
整個(gè)transfer方法幾乎都在一個(gè)自旋操作中完成，從右往左開(kāi)始進(jìn)行數(shù)據(jù)遷移，transfer的退出點(diǎn)是當(dāng)某個(gè)線程處理完最后的table區(qū)段——table[0,stride-1]。
transfer方法主要包含4個(gè)分支，即對(duì)4種不同情況進(jìn)行處理，我們按照難易程度來(lái)解釋下各個(gè)分支所做的事情：
CASE2：桶table[i]為空
當(dāng)舊table的桶table[i] == null，說(shuō)明原來(lái)這個(gè)桶就沒(méi)有數(shù)據(jù)，那就直接嘗試放置一個(gè)ForwardingNode，表示這個(gè)桶已經(jīng)處理完成。
else if ((f = tabAt(tab, i)) == null) // CASE2：舊桶本身為null，不用遷移，直接嘗試放一個(gè)ForwardingNode
advance = casTabAt(tab, i, null, fwd);
注：ForwardingNode我們?cè)谏弦黄岬竭^(guò)，主要做占用位，多線程進(jìn)行數(shù)據(jù)遷移時(shí)，其它線程看到這個(gè)桶中是ForwardingNode結(jié)點(diǎn)，就知道有線程已經(jīng)在數(shù)據(jù)遷移了。
另外，當(dāng)最后一個(gè)線程完成遷移任務(wù)后，會(huì)遍歷所有桶，看看是否都是ForwardingNode，如果是，那么說(shuō)明整個(gè)擴(kuò)容/數(shù)據(jù)遷移的過(guò)程就完成了。
CASE3：桶table[i]已遷移完成
沒(méi)什么好說(shuō)的，就是桶已經(jīng)用ForwardingNode結(jié)點(diǎn)占用了，表示該桶的數(shù)據(jù)都遷移完了。
else if ((fh = f.hash) == MOVED) // CASE3：該舊桶已經(jīng)遷移完成，直接跳過(guò)
advance = true;
CASE4：桶table[i]未遷移完成
如果舊桶的數(shù)據(jù)未遷移完成，就要進(jìn)行遷移，這里根據(jù)桶中結(jié)點(diǎn)的類(lèi)型分為：鏈表遷移、紅黑樹(shù)遷移。
①鏈表遷移
鏈表遷移的過(guò)程如下，首先會(huì)遍歷一遍原鏈表，找到最后一個(gè)相鄰runBit不同的結(jié)點(diǎn)。
runbit是根據(jù)key.hash和舊table長(zhǎng)度n進(jìn)行與運(yùn)算得到的值，由于table的長(zhǎng)度為2的冪次，所以runbit只可能為0或最高位為1
然后，會(huì)進(jìn)行第二次鏈表遍歷，按照第一次遍歷找到的結(jié)點(diǎn)為界，將原鏈表分成2個(gè)子鏈表，再鏈接到新table的槽中?？梢钥吹?，新table的索引要么是i，要么是i+n，這里就利用了上一節(jié)說(shuō)的ConcurrentHashMap的rehash特點(diǎn)。
if (fh >= 0) { // CASE4.1：桶的hash>0，說(shuō)明是鏈表遷移
/**
* 下面的過(guò)程會(huì)將舊桶中的鏈表分成兩部分：ln鏈和hn鏈
* ln鏈會(huì)插入到新table的槽i中，hn鏈會(huì)插入到新table的槽i+n中
*/
int runBit = fh & n; // 由于n是2的冪次，所以runBit要么是0，要么高位是1
Node lastRun = f; // lastRun指向最后一個(gè)相鄰runBit不同的結(jié)點(diǎn)
for (Node p = f.next; p != null; p = p.next) {
int b = p.hash & n;
if (b != runBit) {
runBit = b;
lastRun = p;
}
}
if (runBit == 0) {
ln = lastRun;
hn = null;
} else {
hn = lastRun;
ln = null;
}
// 以lastRun所指向的結(jié)點(diǎn)為分界，將鏈表拆成2個(gè)子鏈表ln、hn
for (Node 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(ph, pk, pv, ln);
else
hn = new Node(ph, pk, pv, hn);
}
setTabAt(nextTab, i, ln); // ln鏈表存入新桶的索引i位置
setTabAt(nextTab, i + n, hn); // hn鏈表存入新桶的索引i+n位置
setTabAt(tab, i, fwd); // 設(shè)置ForwardingNode占位
advance = true; // 表示當(dāng)前舊桶的結(jié)點(diǎn)已遷移完畢
}
②紅黑樹(shù)遷移
紅黑樹(shù)的遷移按照鏈表遍歷的方式進(jìn)行，當(dāng)鏈表結(jié)點(diǎn)超過(guò)/小于閾值時(shí)，涉及紅黑樹(shù)<->鏈表的相互轉(zhuǎn)換：
else if (f instanceof TreeBin) { // CASE4.2：紅黑樹(shù)遷移
/**
* 下面的過(guò)程會(huì)先以鏈表方式遍歷，復(fù)制所有結(jié)點(diǎn)，然后根據(jù)高低位組裝成兩個(gè)鏈表；
* 然后看下是否需要進(jìn)行紅黑樹(shù)轉(zhuǎn)換，最后放到新table對(duì)應(yīng)的桶中
*/
TreeBin t = (TreeBin) f;
TreeNode lo = null, loTail = null;
TreeNode hi = null, hiTail = null;
int lc = 0, hc = 0;
for (Node e = t.first; e != null; e = e.next) {
int h = e.hash;
TreeNode p = new TreeNode
(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;
}
}
// 判斷是否需要進(jìn)行 紅黑樹(shù) <-> 鏈表 的轉(zhuǎn)換
ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :
(hc != 0) ? new TreeBin(lo) : t;
hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
(lc != 0) ? new TreeBin(hi) : t;
setTabAt(nextTab, i, ln);
setTabAt(nextTab, i + n, hn);
setTabAt(tab, i, fwd); // 設(shè)置ForwardingNode占位
advance = true; // 表示當(dāng)前舊桶的結(jié)點(diǎn)已遷移完畢
}
CASE1：當(dāng)前是最后一個(gè)遷移任務(wù)或出現(xiàn)擴(kuò)容沖突
我們剛才說(shuō)了，調(diào)用transfer的線程會(huì)自動(dòng)領(lǐng)用某個(gè)區(qū)段的桶，進(jìn)行數(shù)據(jù)遷移操作，當(dāng)區(qū)段的初始索引i變成負(fù)數(shù)的時(shí)候，說(shuō)明當(dāng)前線程處理的其實(shí)就是最后剩下的桶，并且處理完了。
所以首先會(huì)更新sizeCtl變量，將擴(kuò)容線程數(shù)減1，然后會(huì)做一些收尾工作：
設(shè)置table指向擴(kuò)容后的新數(shù)組，遍歷一遍舊數(shù)組，確保每個(gè)桶的數(shù)據(jù)都遷移完成——被ForwardingNode占用。
另外，可能在擴(kuò)容過(guò)程中，出現(xiàn)擴(kuò)容沖突的情況，比如多個(gè)線程領(lǐng)用了同一區(qū)段的桶，這時(shí)任何一個(gè)線程都不能進(jìn)行數(shù)據(jù)遷移。
if (i < 0 || i >= n || i + n >= nextn) { // CASE1：當(dāng)前是處理最后一個(gè)tranfer任務(wù)的線程或出現(xiàn)擴(kuò)容沖突
int sc;
if (finishing) { // 所有桶遷移均已完成
nextTable = null;
table = nextTab;
sizeCtl = (n << 1) - (n >>> 1);
return;
}
// 擴(kuò)容線程數(shù)減1,表示當(dāng)前線程已完成自己的transfer任務(wù)
if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
// 判斷當(dāng)前線程是否是本輪擴(kuò)容中的最后一個(gè)線程，如果不是，則直接退出
if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
return;
finishing = advance = true;
/**
* 最后一個(gè)數(shù)據(jù)遷移線程要重新檢查一次舊table中的所有桶，看是否都被正確遷移到新table了：
* ①正常情況下，重新檢查時(shí)，舊table的所有桶都應(yīng)該是ForwardingNode;
* ②特殊情況下，比如擴(kuò)容沖突(多個(gè)線程申請(qǐng)到了同一個(gè)transfer任務(wù))，此時(shí)當(dāng)前線程領(lǐng)取的任務(wù)會(huì)作廢，那么最后檢查時(shí)，
* 還要處理因?yàn)樽鲝U而沒(méi)有被遷移的桶，把它們正確遷移到新table中
*/
i = n; // recheck before commit
}
}
