本人是工作7年的老程序员，在头条分享我对Java运用和源码、各种框架运用和源码的认识和理解，如果对您有所帮助，请持续关注。

声明：所有的文章都是自己工作之余一个字一个字码上去的，希望对学习Java的同学有所帮助，如果有理解不到位的地方，欢迎交流。

上一篇文章我对ConcurrentHashMap的非常重要的put方法做了一个全面的解析，但是遗留了两个也非常重要的知识点：扩容和线程安全，接下来两篇文章就围绕这两个内容展开。此篇内容是我经过几天的空闲时间写出来的，由于篇幅过长，请耐心看完，相信对你会有所有帮助，如果有理解不到位的地方，欢迎交流。首先贴出扩容的流程图

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

1：回忆一下HashMap是怎样扩容的
2：ConcurrentHashMap什么时候会进行扩容
3：ConcurrentHashMap的扩容详解

一、回忆一下HashMap是怎样扩容的

在HashMap中数组的初始化和扩容用的是同一个方法，相对ConcurrentHashMap还是比较容易理解的，下面我就对HashMap的扩容总结一下以及什么时候才进行扩容，非常详细的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，则是原来的位置，具体的请看HashMap扩容机制

2：HashMap什么是否才会进行扩容

因为初始化和扩容是同一个方法，所以主要有两个部分用到
1：当第一次调用put时进行初始化工作
2：当加入新的元素时，如果集合元素大于了阀门，就会调用扩容方法

HashMap的调用内容如图所示：

二、ConcurrentHashMap什么时候会进行扩容

通过读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的流程图如下：

2：helpTransfer方法中

我在分析ConcurrentHashMap的put方法中讲到过这个helpTransfer方法，主要是协助其他线程进行扩容，详细的分析请看哪一篇文章，helpTransfer的流程图如下：

3：tryPresize方法中

从字面上理解这个方法的含义就是尝试扩容，主要有两个地方调用了这个方法，如图

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<K,V>[] 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<K,V>[] nt = (Node<K,V>[])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<K,V>[] 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的流程图如下：

三、ConcurrentHashMap的扩容详解

上面我们了解了什么时候会调用transfer方法，也了解了HashMap的扩容非常的简单，它不用考虑多线程的情况，但是ConcurrentHashMap就不一样了，它需要考虑多线程的情况，并且为了性能的原因，Doug Lea大神设计了其他线程协助扩容的机制，所以它的扩容变得比较复杂了，接下来我们详细分析它的扩容机制是怎样设计的。

分析扩容细节之前，我总结了扩容的两个要点：

第一个要点：底层数组的扩容：一般会扩大到原来的两倍，并且只允许一个线程进行，不允许多线程并发扩大数组的长度。
第二个要点：数据的迁移，就是把已存在的元素迁移到新的数组中。这个阶段可以多线程并发辅助扩容。

那在扩容时，transfer方法怎样体现出这两个要点呢？如图：

上面我们分析了什么时候调用transfer方法，只有当前线程为第一个扩容线程时，transfer的第二个参数才为null,所以只能是第一个扩容线程才能扩大数组的容量。下面的for循环就是对老数据的迁移工作了。

我们结合上面两个要点开始对transfer方法进行详细的分析，还是老原则，贴出transfer的源代码。

第一个要点：扩大数组的长度

private final void transfer(Node<K,V>[] tab, Node<K,V>[] 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<K,V>[] nt = (Node<K,V>[])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<K,V>[] 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<K,V> fwd = new ForwardingNode<K,V>(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<K,V> 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循环已经计算出了当前线程要迁移数据数组下标的范围，那么接下来就要进行真正的迁移数据了，接下来我们看看怎样迁移的。我们首先看一些简化的代码

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的机制相同，如果不熟悉，请看HashMap的文章。这里我就不在重复这些内容了。上面我们就完整分析了ConcurrentHashMap的扩容机制，为了让流程更加的清晰，我接下来用一个流程图来分析。