本人是工作7年的老程序員，在頭條分享我對Java運用和源碼、各種框架運用和源碼的認識和理解，如果對您有所幫助，請持續關注。

聲明：所有的文章都是自己工作之餘一個字一個字碼上去的，希望對學習Java的同學有所幫助，如果有理解不到位的地方，歡迎交流。

上一篇文章我對ConcurrentHashMap的非常重要的put方法做了一個全面的解析，但是遺留了兩個也非常重要的知識點：擴容和線程安全，接下來兩篇文章就圍繞這兩個內容展開。此篇內容是我經過幾天的空閒時間寫出來的，由於篇幅過長，請耐心看完，相信對你會有所有幫助，如果有理解不到位的地方，歡迎交流。首先貼出擴容的流程圖

ConcurrentHashMap擴容的流程圖

本篇文章的主要內容如下：

1：回憶一下HashMap是怎樣擴容的
2：ConcurrentHashMap什麼時候會進行擴容
3：ConcurrentHashMap的擴容詳解

一、回憶一下HashMap是怎樣擴容的

在HashMap中數組的初始化和擴容用的是同一個方法，相對ConcurrentHashMap還是比較容易理解的，下面我就對HashMap的擴容總結一下以及什麼時候才進行擴容，非常詳細的HashMap擴容機制請看

1：HashMap的擴容總結

1：首先判斷數組是否被初始化，如果沒有被初始化，則進行初始化工作，判斷是否被初始化的條件：table==null || table.length==0
2：如果是初始化，根據不同的構造函數進行初始化：
2.1：如果是無參構造函數，則默認數組的長度為16，擴容閥門為16*0.75=12
2.2：如果是有參數構造函數，則數組的長度就是threshold.
3：如果已經初始化了，判斷條件：int oldCap = (oldTab == null) ? 0 : oldTab.length>0
擴容規則：數組的長度擴大為原來的2倍，擴容閥門threshold擴大為原來的2倍。 

4：遷移老數據：
4.1：如果老的下標只有一個元素，則直接通過(newCap-1)&hash計算出新的下標
4.2：如果老的下標是一個紅黑樹，則利用紅黑樹的遷移規則
4.3：如果老的下標是一個鏈表，則利用鏈表的遷移規則

HashMap遷移紅黑樹和鏈表時做了一個優化，因為HashMap數組的長度都是2的n次方冪，所以數組長度擴大2倍後，用二進制表示：前面多出了一個高位1，所以元素放到原來的位置，還是原來位置+oldCap,就要看這個元素和多出那一個高位1是怎樣的了，如果元素的那一位也是1，則是原來的位置+oldCap,如果是0，則是原來的位置，具體的請看

2：HashMap什麼是否才會進行擴容

因為初始化和擴容是同一個方法，所以主要有兩個部分用到
1：當第一次調用put時進行初始化工作
2：當加入新的元素時，如果集合元素大於了閥門，就會調用擴容方法

HashMap的調用內容如圖所示：

二、ConcurrentHashMap什麼時候會進行擴容

通過讀ConcurrentHashMap的源碼知道，擴容的主要工作就在transfer方法中，我們稍後會對這個方法進行詳細的講解，接下來我們看看ConcurrentHashMap中哪些地方調用了transfer進行擴容的。如下圖所示

ConcurrentHashMap調用transfer的地方

接下來我們一個一個的去分析。

1：addCount方法中：

while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
 (n = tab.length) < MAXIMUM_CAPACITY) {
//進入while循環：說明當前的元素數量大於了sizeCtrl，就需要擴容了。
 int rs = resizeStamp(n);
if (sc < 0) {
//走到這一步：說明sizeCtrl<0,說明正在擴容，所以需要當前線程協助擴容，需要不需要協助需要進行判斷
 if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
 sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
 transferIndex <= 0)
//走到這一步：說明不需要協助了。
 break; 

 if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
//走到這一步：說明需要進行協助擴容，上面的CAS操作就是將擴容線程+1.
 transfer(tab, nt);
}
else if (U.compareAndSwapInt(this, SIZECTL, sc,
 (rs << RESIZE_STAMP_SHIFT) + 2))
//走到這一步：說明當前線程是第一個擴容的線程
 transfer(tab, null);
}

addCount方法會在putVal()方法最後調用，有主要有兩個作用：

1：高併發的對元素的總數進行操作，也就是對CounterCell和baseCount的操作。
1.1：如果沒有併發，每增加一個元素就利用CAS機制增加baseCount.
1.2：如果有併發，則通過操作CounterCell數組。
2：判斷是否需要擴容。
2.1:如果sizeCtrl<0:說明其他線程正在擴容，當前線程就需要判斷是否能夠輔助擴容了。
2.2：如果sizeCtrl>0：說明還沒有其他線程進行擴容，當前線程是第一個擴容的線程。

兩個調用的地方還是有區別的，如果是輔助其他線程進行擴容則transfer的最後一個參數不為空，如果當前線程是第一個擴容的線程，則最後一個參數為空。addCount的流程圖如下：

addCount方法的流程圖

2：helpTransfer方法中

我在分析 講到過這個helpTransfer方法，主要是協助其他線程進行擴容，詳細的分析請看哪一篇文章，helpTransfer的流程圖如下：

helpTransfer方法的流程圖

3：tryPresize方法中

從字面上理解這個方法的含義就是嘗試擴容，主要有兩個地方調用了這個方法，如圖

調用tryresize方法的地方

1：putAll()方法：把給定的Map集合加入到ConcurrentHashMap中
2：treeifyBin()方法：這個方式是在鏈表轉換成紅黑樹的時候，所以當鏈表長度大於8時，鏈表不一定就轉換成紅黑樹，如果此時底層數組的長度小於64，則進行擴容，否則將鏈表轉換成紅黑樹 

tryPresize的源代碼如下：

private final void tryPresize(int size) {
 int c = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY :
 tableSizeFor(size + (size >>> 1) + 1);
 int sc;
 while ((sc = sizeCtl) >= 0) {
 Node[] tab = table; int n;
 if (tab == null || (n = tab.length) == 0) {
//走到這一步$1:說明數組還未初始化，則進行初始化工作，和initTab的方法流程一樣。
 n = (sc > c) ? sc : c;
 if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
 try {
 if (table == tab) {
 @SuppressWarnings("unchecked")
 Node[] nt = (Node[])new Node,?>[n];
 table = nt;
 sc = n - (n >>> 2);
 }
 } finally {
 sizeCtl = sc;
 }
 }
 }
 else if (c <= sc || n >= MAXIMUM_CAPACITY)
//走到這一步$2:說明不需要進行擴容或者容量已經達到最大
 break;
 else if (tab == table) {
//走到這一步$3：嘗試進行擴容或者輔助其他線程進行擴容了
 int rs = resizeStamp(n);
 if (sc < 0) {
 Node[] nt;
 if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
 sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
 transferIndex <= 0)
1：(sc >>> RESIZE_STAMP_SHIFT) != rs:表示已經擴容結束 

2：sc == rs + 1 || sc == rs + MAX_RESIZERS：這兩個判斷是擴容線程已經達到最大，但是在ConcurrentHashMap中這兩個永遠都是false
3： (nt = nextTable) == null || transferIndex <= 0：表示擴容結束
//走到這一步：說明不需要進行協助擴容
 break;
 if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
//通過CAS將擴容線程+1，成功後則協助進行擴容
 transfer(tab, nt);
 }
 else if (U.compareAndSwapInt(this, SIZECTL, sc,
 (rs << RESIZE_STAMP_SHIFT) + 2))
//當前線程是第一個擴容的線程。
 transfer(tab, null);
 }
 }
}

tryPresize()方法主要有3個分支流程：

$1：判斷底層數組是否被初始化，如果沒有初始化則進行初始化，這個在putAll時會出現，而treeifyBin不會進入這個條件中
$2：我們講過sizeCtrl，如果元素的數量大於等於sizeCtrl時將會進行擴容：c<=sc，如果不符合這個條件，則無需擴容，如果sizeCtrl達到了最大值，則也不能擴容了。
$3:這一步就是嘗試進行擴容了，首先要判斷當前線程是否能夠進行擴容或者協助擴容
第一個條件：(sc >>> RESIZE_STAMP_SHIFT) != rs：表明已經擴容結束了。 

第二個條件和第三個條件：sc == rs + 1 || sc == rs + MAX_RESIZERS：這兩個條件表示擴容線程已經達到了最大值，當前線程不能進行擴容了，但是在ConcurrentHashMap中這兩個條件永遠都是false
第四個條件和第五個條件：表示擴容結束了
如果這5個條件任意一個為true，則當前線程不需要擴容或者協助擴容了，直接跳出循環。
如果這5個條件都是false，則需要判斷是否正在擴容，如果正在擴容，則協助其他線程進行擴容，如果沒有進行擴容，則當前線程是第一個擴容線程。

tryPresize的流程圖如下：

tryPresize方法的流程圖

三、ConcurrentHashMap的擴容詳解

上面我們瞭解了什麼時候會調用transfer方法，也瞭解了HashMap的擴容非常的簡單，它不用考慮多線程的情況，但是ConcurrentHashMap就不一樣了，它需要考慮多線程的情況，並且為了性能的原因，Doug Lea大神設計了其他線程協助擴容的機制，所以它的擴容變得比較複雜了，接下來我們詳細分析它的擴容機制是怎樣設計的。

分析擴容細節之前，我總結了擴容的兩個要點：

第一個要點：底層數組的擴容：一般會擴大到原來的兩倍，並且只允許一個線程進行，不允許多線程併發擴大數組的長度。
第二個要點：數據的遷移，就是把已存在的元素遷移到新的數組中。這個階段可以多線程併發輔助擴容。

那在擴容時，transfer方法怎樣體現出這兩個要點呢？如圖：

擴容兩個要點的源碼截圖

上面我們分析了什麼時候調用transfer方法，只有當前線程為第一個擴容線程時，transfer的第二個參數才為null,所以只能是第一個擴容線程才能擴大數組的容量。下面的for循環就是對老數據的遷移工作了。

我們結合上面兩個要點開始對transfer方法進行詳細的分析，還是老原則，貼出transfer的源代碼。

第一個要點：擴大數組的長度

private final void transfer(Node[] tab, Node[] nextTab) {
 int n = tab.length, stride;
//stride:在數據遷移時，每一個線程要負責遷移老數組table的多少個桶(數組下標)
 if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
 stride = MIN_TRANSFER_STRIDE; // subdivide range
 if (nextTab == null) { // initiating
//走到這一步：只有第一個擴容線程才能走到這一步，創建一個新的Node數組，長度是原來數組的2倍。
 try {
 @SuppressWarnings("unchecked")
 Node[] nt = (Node[])new Node,?>[n << 1];
 nextTab = nt;
 } catch (Throwable ex) { // try to cope with OOME
 sizeCtl = Integer.MAX_VALUE;
 return;
 }
 //將創建的新的數組賦值給nextTable.將老數組的長度賦值給transferIndex 

 nextTable = nextTab;
 transferIndex = n;
 }
 //.....遷移老的數據，等會分析
}

上面的代碼要理解如下內容：

1：n:老數組的長度
2：stride:在數據遷移時，每一個線程負責遷移老數組的多少個桶(也就是數組的下標)，最少為16個，所以從這可以看出，如果利用默認的構造函數創建Map，第一次擴容時只能有一個線程進行擴容，因為n=16.
3:nextTable:全局變量，private transient volatile Node[] nextTable：只有在擴容時才不為空。
4：新數組的長度變成老數組的2倍。
5：transferIndex：擴容線程要遷移下標的標記，從老數組的末尾到首部(從右到左)進行數據遷移。例如：
第一個擴容線程要遷移的桶：[transferIndex-stride,transferIndex-1]
第二個擴容線程要遷移的桶：[transferIndex-2*stride,transferIndex-stride-1]
最後一個擴容線程要遷移的桶：[0,stride-1]

上面的把數組擴大到原來的2倍沒有什麼難度了，一些變量我也做了說明，接下來我們看看怎樣把老數組中的數據遷移到新的數組中去。

第一部分代碼：

int nextn = nextTab.length;
//擴容時的節點封裝，當一個下標的數據遷移完成後，會被標成ForwardingNode
ForwardingNode fwd = new ForwardingNode(nextTab);
//表示老數組的一個下標的數據是否遷移完成
boolean advance = true;
//最後一個協助擴容線程會把此值設置成true,表明數據遷移完成。
boolean finishing = false;
//i:表示遷移老數組中的下標
//bound:表示一個擴容線程遷移的最後一個桶(最後一個下標)，因為遷移數據是從右到左的。
//i和bound就是代表的[bound=transferIndex-stride,i=transferIndex-1]。
//for循環：遷移[bound,i]之間的數據。
for (int i = 0, bound = 0;;) {
 Node f; int fh;
//while循環：計算出當前線程要遷移數據的下標範圍，例如[bound=0,i=15]
 while (advance) {
 int nextIndex, nextBound;
 if (--i >= bound || finishing)
//走到這一步$1：說明當前線程已經計算出了要負責遷移的數據範圍
 advance = false;
 else if ((nextIndex = transferIndex) <= 0) {
//走到這一步$2：說明數據已經遷移完成了，無需在遷移了。
 i = -1; 

 advance = false;
 }
 else if (U.compareAndSwapInt
 (this, TRANSFERINDEX, nextIndex,
 nextBound = (nextIndex > stride ?
 nextIndex - stride : 0))) {
//走到這一步$3:說明計算出當前線程要計算出負責遷移數據的範圍
 bound = nextBound;
 i = nextIndex - 1;
 advance = false;
 }
 }

上面的代碼總結如下：

1：while循環的意思：計算出當前線程要遷移數據的數組下標範圍[bound,i]
2：for循環的意思：就是從右到左開始遷移數據，就是從i開始遷移數據，直到bound結束，當前線程遷移數據結束。

1

為了更好的理解這個while循環，舉例如下：

一個線程進入了while循環，此時i=0,bound=0.

1：首先判斷if語句，不符合，繼續判斷
2：進入else if語句，nextIndex=transferIndex=16>0,不符合，繼續判斷
3：進入else if語句。通過CAS判斷，成功後 

nextIndex=16.
nextBound=0:通過計算很容易獲取。所以bound=0.
i=nextIndex-1=15.
所以計算出當前線程遷移數組的下標[bound,i]=[0,15],但是不是從bound到i遷移的，而是從i到bound倒著遷移的。

while循環計算i和bound

上面通過while循環已經計算出了當前線程要遷移數據數組下標的範圍，那麼接下來就要進行真正的遷移數據了，接下來我們看看怎樣遷移的。我們首先看一些簡化的代碼

for (int i = 0, bound = 0;;) {
 while (advance){
 //while上面已經分析，這裡代碼省略
 }
if (i < 0 || i >= n || i + n >= nextn) {
 //$1：已經遷移完成，進行一些掃尾工作
}
else if ((f = tabAt(tab, i)) == null){
//$2：此數組下標沒有數據
}
else if ((fh = f.hash) == MOVED)
 //$3：此數組下標已經遷移過了
else {
//$4：開始遷移，要麼是鏈表、要麼是紅黑樹
}
}
 

通過上面簡化的代碼可以看出，通過while循環獲取到遷移數組的下標範圍後，通過for循環迭代計算的下標範圍，然後通過條件語句進入不同的邏輯，下面我們詳細分析這些條件語句。

1：$1：已經遷移完成，需要進行掃尾工作

if (i < 0 || i >= n || i + n >= nextn) {
int sc;
if (finishing) {
//進入這一步：將新的數組賦值給全局變量table，sizeCtrl變成0.75table.length.遷移完成，退出無限循環。
nextTable = null; 

table = nextTab;
sizeCtl = (n << 1) - (n >>> 1);
return;
}
if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
//進入這一步：通過CAS將遷移線程-1成功後進入。
if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
//進入這一步：說明所有的遷移數據的線程已經沒有了，退出循環
return;
finishing = advance = true;
i = n; // recheck before commit
}
}

2：$2:此數組下標沒有數據，將此下標標記為ForwardingNode節點

else if ((f = tabAt(tab, i)) == null)
 advance = casTabAt(tab, i, null, fwd);

3：$3:此下標已經是ForwardingNode節點，說明此下標已經遷移過

else if ((fh = f.hash) == MOVED)
 advance = true; // already processed

4：$4:開始遷移數據，要麼遷移的是鏈表，要麼遷移的是紅黑樹

else {
//遷移一個下標數據時，要加鎖。
 synchronized (f) { 

 //此數組和HashMap的遷移類似，這裡就不在把代碼貼出來了。
 }
}

上面遷移鏈表和紅黑樹時，和HashMap的機制相同，如果不熟悉，請看 。這裡我就不在重複這些內容了。上面我們就完整分析了ConcurrentHashMap的擴容機制，為了讓流程更加的清晰，我接下來用一個流程圖來分析。

ConcurrentHashMap擴容的流程圖

閱讀更多 強哥Java架構之路 的文章

關鍵字: 知識點 解析 程序員