java的hashmap如何使用：Java集合系列-ConcurrentHashMap-扩容机制的全面解析

java的hashmap如何使用：Java集合系列-ConcurrentHashMap-扩容机制的全面解析2：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：

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

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

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

ConcurrentHashMap扩容的流程图

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

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进行扩容的。如下图所示

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方法中

我在分析ConcurrentHashMap的put方法中讲到过这个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<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的流程图如下：

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循环计算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的扩容机制，为了让流程更加的清晰，我接下来用一个流程图来分析。

ConcurrentHashMap扩容的流程图