ConcurrentHashMap的put方法

public V put(K key, V value) {return putVal(key, value, false);}final V putVal(K key, V value, boolean onlyIfAbsent) {if (key == null || value == null) throw new NullPointerException();int hash = spread(key.hashCode());   //@1，讲解见下面小标题。//i处结点数量，2: TreeBin或链表结点数, 其它：链表结点数。主要用于每次加入结点后查看是否要由链表转为红黑树int binCount = 0; for (Node<K,V>[] tab = table;;) {   //CAS经典写法，不成功无限重试，让再次进行循环进行相应操作。Node<K,V> f; int n, i, fh;//除非构造时指定初始化集合，否则默认构造不初始化table，所以需要在添加时元素检查是否需要初始化。if (tab == null || (n = tab.length) == 0)tab = initTable();  //@2//CAS操作得到对应table中元素else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { //@3if (casTabAt(tab, i, null,new Node<K,V>(hash, key, value, null)))break;                   //null创建Node对象做为链表首结点}else if ((fh = f.hash) == MOVED)  //当前结点正在扩容//让当前线程调用helpTransfer也参与到扩容过程中来，扩容完毕后tab指向新table。tab = helpTransfer(tab, f); else {V oldVal = null;synchronized (f) {if (tabAt(tab, i) == f) {  //双重检查i处结点未变化if (fh >= 0) {  //表明是链表结点类型，hash值是大于0的，即spread()方法计算而来binCount = 1;for (Node<K,V> e = f;; ++binCount) {K ek;if (e.hash == hash &&((ek = e.key) == key ||(ek != null && key.equals(ek)))) {oldVal = e.val;//onlyIfAbsent表示是新元素才加入，旧值不替换，默认为fase。if (!onlyIfAbsent)  e.val = value;break;}Node<K,V> pred = e;if ((e = e.next) == null) {//jdk1.8版本是把新结点加入链表尾部，next由volatile修饰pred.next = new Node<K,V>(hash, key,value, null);break;}}}else if (f instanceof TreeBin) {  //红黑树结点类型Node<K,V> p;binCount = 2;if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,value)) != null) {   //@4oldVal = p.val;if (!onlyIfAbsent)p.val = value;}}}}if (binCount != 0) {if (binCount >= TREEIFY_THRESHOLD)  //默认桶中结点数超过8个数据结构会转为红黑树treeifyBin(tab, i);   //@5if (oldVal != null)return oldVal;break;}}}addCount(1L, binCount);  //更新size，检测扩容return null;}

6-14检查key，value是否为空，如果是则抛出异常，并且检查table数组是否初始化了如果没有则触发initTable函数（后面讲）。
16-20行主要是利用cas原理检查经过hash计算后key所放tabe角标处是否有值，如果为null则利用cas原理创建一个Node。
21-23行主要是检查数组是否处在扩容模式，如果是则启动协助扩容（后面单讲），协助完成后tab就是扩容后的数组。
26-49行，首先对定位到的数组角标位加锁，再次判断角标头结点是否被修改，如果没有，检查fh（就是此处的key的hash是否大于0，大于0则表明是经过spread计算后的即是一个链表结构）那么我们就遍历链表，如果遍历过程中找到了则将找到的值付给oldVal，如果没有找到则（（e=e.next）==null）那么就在尾部加入新传入的节点。
50-61行为如果节点类型为红黑树（这里的TreeBin是将红黑树结构包含进来的一个结构）就也是遍历，没有则插入。
62-70行判断binCount是否不等于0，因为bincount初始值为0，只有当判断结构为链表的时候后才用来计算链表的元素个数，所以这里判断如果bincount大于8这个阈值则进行树化。
71 addCount行我们可以理解为更新hashmap的元素个数，并检测是否就扩容。

initTable函数的理解

initTable()用于里面table数组的初始化，值得一提的是table初始化是没有加锁的，那么如何处理并发呢？
由下面代码可以看到，当要初始化时会通过CAS操作将sizeCtl置为-1，而sizeCtl由volatile修饰，保证修改对后面线程可见。
这之后如果再有线程执行到此方法时检测到sizeCtl为负数，说明已经有线程在给扩容了，这个线程就会调用Thread.yield()让出一次CPU执行时间。

private final Node<K,V>[] initTable() {Node<K,V>[] tab; int sc;while ((tab = table) == null || tab.length == 0) {if ((sc = sizeCtl) < 0)Thread.yield(); //正在初始化时将sizeCtl设为-1else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {try {if ((tab = table) == null || tab.length == 0) {int n = (sc > 0) ? sc : DEFAULT_CAPACITY;  //DEFAULT_CAPACITY为16@SuppressWarnings("unchecked")Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];table = tab = nt;sc = n - (n >>> 2);   //扩容阈值为新容量的0.75倍}} finally {sizeCtl = sc;   //扩容保护}break;}}return tab;}

第4-5行就是我们的检测如果sizeCtl<0则表明已经有其他线程对此数组进行扩容那么就释放此次机会，7-15在配合上我们的外层的while则组成了一个自旋锁，来保证我们的线程安全，（volitile关键字保证了sizeCtl的线程可见性），try代码块中，就是具体的初始化过程，最后值得注意的是将sc=n-（n>>>2）表明n-1/4n=0.75n实际就是我们的判断是否扩容的阈值之后在返回新的tab。

扩容

什么时候扩容

• 使用put()添加元素时会调用addCount()，内部检查sizeCtl看是否需要扩容。
• tryPresize()被调用，此方法被调用有两个调用点：
• 链表转红黑树(put()时检查)时如果table容量小于64(MIN_TREEIFY_CAPACITY)，则会触发扩容。
• 调用putAll()之类一次性加入大量元素，会触发扩容。

我们先看看addCount是怎么实现的

addCount

  private final void addCount(long x, int check) {CounterCell[] as; long b, s;if ((as = counterCells) != null ||!U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {CounterCell a; long v; int m;boolean uncontended = true;if (as == null || (m = as.length - 1) < 0 ||(a = as[ThreadLocalRandom.getProbe() & m]) == null ||!(uncontended =U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {fullAddCount(x, uncontended);return;}if (check <= 1)return;s = sumCount();}//check就是结点数量，有新元素加入成功才检查是否要扩容。if (check >= 0) {Node<K,V>[] tab, nt; int n, sc;//s表示加入新元素后容量大小，计算已省略。//新容量大于当前扩容阈值并且小于最大扩容值才扩容，如果tab=null说明正在初始化，死循环等待初始化完成。while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&(n = tab.length) < MAXIMUM_CAPACITY) {int rs = resizeStamp(n);  //@1//sc<0表示已经有线程在进行扩容工作if (sc < 0) {//条件1：检查是对容量n的扩容，保证sizeCtl与n是一块修改好的//条件2与条件3：应该是进行sc的最小值或最大值判断。//条件4与条件5: 确保tranfer()中的nextTable相关初始化逻辑已走完。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))  //有新线程参与扩容则sizeCtl加1transfer(tab, nt);}//没有线程在进行扩容，将sizeCtl的值改为(rs << RESIZE_STAMP_SHIFT) + 2)，原因见下面sizeCtl值的计算分析。else if (U.compareAndSwapInt(this, SIZECTL, sc,(rs << RESIZE_STAMP_SHIFT) + 2))transfer(tab, null);s = sumCount();}}}

在谈论addCount代码之前我们先来理解一下ConcurrentHashMap1.8的元素加1的操作

元素增加的操作

我们在1.7中由于对数组的扩容其实是对segment底下的局部数组扩容而并非所以的，每个segment中维护了一个count变量来计算此segment中元素的个数，当达到阈值时进行扩容，而我们在1.8的currentHashMap中并没有才有segment的结构，那么我们怎么计算合适扩容呢？
在1.8中他将所有的数组元素同一增加，但如果只有一个变量来统计元素个数那势必造成线程的阻塞很严重，那为了解决这一问题，1.8中还有个叫做counterCells的数组，当检测到我们用于统计元素个数的变量BASECOUNT被其他线程所占有的时候就会通过计算hash值取出counterCells对应角标的countCell来对其进行+1操作，最后在统一付给我们的BASECOUNT变量，这就使得线程阻塞的概率变小了。

源码解读

我们先看一下参数，为long x，和一个check，这个check对应我们可以在put函数中传入的是（1L，binCount），他是拿bincount来进行判断的。我们看到上来就开始利用cas对BASECOUNT参数进行+x（x传入的为1L）如果失败了或者counterCells数组为null有一个成立，则第二个if判断的是要么countCells为null或者countCells对应角标的值为null，并且对CELLVALUE参数进行+1操作失败，那么就会走一个叫做fullAddCount的函数，这个函数可以保证+1操作肯定完成。
也就是走完前13行+1操作必定完成，此时我们看到有队check进行了<=1的判断，因为我们在外层的put时候，如果是链表结构那么binCount=check=1，然后在对链表遍历的时候会进行++操作，意思是如果链表元素增加成功了那么check必定>=1,而当我们的元素是红黑树的时候那么我们的bincount=check=2也是大于等于1的，也就是说只要元素增加了check必定大于1了，那没大于1所以反回了不用++操作了。如果不满足那么我们就再走到了sumCount函数，这个函数的意义就是把我们countCells数组里面的值加到BASECOUNT里面呢。此时s就是我们整个hashMap元素的个数了。
之后的一个if操作就是我们的扩容操作了，首先是一个while循环条件为s>sizeCtl即元素个数达到了阈值且table不为null并且table长度没有达到上限就满足，之后的resizeStamp（n）只要是这个函数返回的值对其进行左移RESIZE_STAMP_SHIFT位那么他的值必定为一个负数，之后的if（sc<0）因为只要是满足了while的条件sc第一次进来的化不会是负数（因为在while条件中sc=sizectl了），那么就会走

else if (U.compareAndSwapInt(this, SIZECTL, sc,(rs << RESIZE_STAMP_SHIFT) + 2))

这句话对我们rs=resizeStamp（n）的rs进行了rs << RESIZE_STAMP_SHIFT)，那么sc必定为一个负值如果修改成功，然后调用transfer函数进行了扩容操作，当我们此时再有线程进来的时候，因为sc已经为负数了，就只会走if (sc < 0) 条件了，这时候就调用了==transfer（tab，nt）==了，这个函数的具体过程在后边讲到。扩容完毕后重新统计了s的数量。

transfer函数并发扩容

jdk1.8版本的ConcurrentHashMap支持并发扩容，上面已经分析了一小部分，下面这个方法是真正进行并行扩容的地方。

private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {int n = tab.length, stride;if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)  //每个线程处理桶的最小数目，可以看出核数越高步长越小，最小16个。stride = MIN_TRANSFER_STRIDE; // subdivide rangeif (nextTab == null) {try {@SuppressWarnings("unchecked")Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];  //扩容到2倍nextTab = nt;} catch (Throwable ex) {      // try to cope with OOMEsizeCtl = Integer.MAX_VALUE;  //扩容保护return;}nextTable = nextTab;transferIndex = n;  //扩容总进度，>=transferIndex的桶都已分配出去。}int nextn = nextTab.length;//扩容时的特殊节点，标明此节点正在进行迁移，扩容期间的元素查找要调用其find()方法在nextTable中查找元素。ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab); //当前线程是否需要继续寻找下一个可处理的节点boolean advance = true;boolean finishing = false; //所有桶是否都已迁移完成。for (int i = 0, bound = 0;;) {Node<K,V> f; int fh;//此循环的作用是确定当前线程要迁移的桶的范围或通过更新i的值确定当前范围内下一个要处理的节点。while (advance) {int nextIndex, nextBound;if (--i >= bound || finishing)  //每次循环都检查结束条件advance = false;//迁移总进度<=0，表示所有桶都已迁移完成。else if ((nextIndex = transferIndex) <= 0) {  i = -1;advance = false;}else if (U.compareAndSwapInt(this, TRANSFERINDEX, nextIndex,nextBound = (nextIndex > stride ?nextIndex - stride : 0))) {  //transferIndex减去已分配出去的桶。//确定当前线程每次分配的待迁移桶的范围为[bound, nextIndex)bound = nextBound;i = nextIndex - 1;advance = false;}}//当前线程自己的活已经做完或所有线程的活都已做完，第二与第三个条件应该是下面让"i = n"后，再次进入循环时要做的边界检查。if (i < 0 || i >= n || i + n >= nextn) {int sc;if (finishing) {  //所有线程已干完活，最后才走这里。nextTable = null;table = nextTab;  //替换新tablesizeCtl = (n << 1) - (n >>> 1); //调sizeCtl为新容量0.75倍。return;}//当前线程已结束扩容，sizeCtl-1表示参与扩容线程数-1。if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {//还记得addCount()处给sizeCtl赋的初值吗？相等时说明没有线程在参与扩容了，置finishing=advance=true，为保险让i=n再检查一次。if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)   return;finishing = advance = true;i = n; // recheck before commit}}else if ((f = tabAt(tab, i)) == null)advance = casTabAt(tab, i, null, fwd);  //如果i处是ForwardingNode表示第i个桶已经有线程在负责迁移了。else if ((fh = f.hash) == MOVED)advance = true; // already processedelse {synchronized (f) {  //桶内元素迁移需要加锁。if (tabAt(tab, i) == f) {Node<K,V> ln, hn;if (fh >= 0) {  //>=0表示是链表结点//由于n是2的幂次方（所有二进制位中只有一个1)，如n=16(0001 0000)，第4位为1，那么hash&n后的值第4位只能为0或1。所以可以根据hash&n的结果将所有结点分为两部分。int runBit = fh & n;Node<K,V> lastRun = f;//找出最后一段完整的fh&n不变的链表，这样最后这一段链表就不用重新创建新结点了。for (Node<K,V> 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之前的结点因为fh&n不确定，所以全部需要重新迁移。for (Node<K,V> 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<K,V>(ph, pk, pv, ln);elsehn = new Node<K,V>(ph, pk, pv, hn);}//低位链表放在i处setTabAt(nextTab, i, ln);//高位链表放在i+n处setTabAt(nextTab, i + n, hn);setTabAt(tab, i, fwd);  //在原table中设置ForwardingNode节点以提示该桶扩容完成。advance = true;}else if (f instanceof TreeBin) { //红黑树处理。

                        ...

首先我们用一个图来说明整个转移的逻辑过程：

接下来我们看代码实现：

1. 第一个if就是在计算步长。
2. 第二个if进行扩容为原数组两倍。
3. for循环初始化bound和i
4. while里面的逻辑就是在计算本次的bound和i并将advance赋值为false，而advance的意思是是否继续往前移动i，显然我们在计算完i后应该移动，移动完成后才会在将advance赋值为true。
5. 当advance为false后看我们的这段代码：

 else if ((f = tabAt(tab, i)) == null)advance = casTabAt(tab, i, null, fwd);  //如果i处是ForwardingNode表示第i个桶已经有线程在负责迁移了。else if ((fh = f.hash) == MOVED)advance = true; // already processed

意思为图中的4，后个if为如果此标记位是moved就是为了避免误判。
6. 之后的代码块就是在转移元素，因为转移过程要是线程安全的所以加锁。过程同hashmap一致。
7. 转移完成后当此时bound同i的条件–i >= bound不满足了那么再将advance赋值为true重复上述过程。

上面的过程为当我们一个线程操作时候的场景，当此时又有一个线程进来时，那么经过while计算过后必定bound和i是没有转移过得范围那么当前线程也重新计算bound和i做上述过程，两个线程间互不烦扰。

helpTransfer函数

添加、删除节点之处都会检测到table的第i个桶是ForwardingNode的话会调用helpTransfer()方法。

final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {Node<K,V>[] nextTab; int sc;if (tab != null && (f instanceof ForwardingNode) &&(nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {int rs = resizeStamp(tab.length);while (nextTab == nextTable && table == tab &&(sc = sizeCtl) < 0) {if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||sc == rs + MAX_RESIZERS || transferIndex <= 0)break;if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {transfer(tab, nextTab);break;}}return nextTab;}

上述过程也主要是调用transfer方法不再赘述。

并发扩容总结

1. 单线程新建nextTable，新容量一般为原table容量的两倍。
2. 每个线程想增/删元素时，如果访问的桶是ForwardingNode节点，则表明当前正处于扩容状态，协助一起扩容完成后再完成相应的数据更改操作。
3. 扩容时将原table的所有桶倒序分配，每个线程每次最小分配16个桶，防止资源竞争导致的效率下降。单个桶内元素的迁移是加锁的，但桶范围处理分配可以多线程，在没有迁移完成所有桶之前每个线程需要重复获取迁移桶范围，直至所有桶迁移完成。
4. 一个旧桶内的数据迁移完成但不是所有桶都迁移完成时，查询数据委托给ForwardingNode结点查询nextTable完成（这个后面看find()分析）。
5. 迁移过程中sizeCtl用于记录参与扩容线程的数量，全部迁移完成后sizeCtl更新为新table容量的0.75倍。