简书 占小狼 转载请注明原创出处，谢谢！
此谓知本，此谓知之至也 《礼记·大学》
1、深入浅出ConcurrentHashMap（1.8）
2、谈谈ConcurrentHashMap1.7和1.8的不同实现
3、ConcurrentHashMap的红黑树实现分析
ConcurrentHashMap相关的文章写了不少，有个遗留问题一直没有分析，也被好多人请教过，被搁置在一旁，即如何在并发的情况下实现数组的扩容。
什么情况会触发扩容
当往hashMap中成功插入一个key/value节点时，有可能触发扩容动作：
1、如果新增节点之后，所在链表的元素个数达到了阈值 8，则会调用treeifyBin方法把链表转换成红黑树，不过在结构转换之前，会对数组长度进行判断，实现如下：
如果数组长度n小于阈值MIN_TREEIFY_CAPACITY，默认是64，则会调用tryPresize方法把数组长度扩大到原来的两倍，并触发transfer方法，重新调整节点的位置。
2、新增节点之后，会调用addCount方法记录元素个数，并检查是否需要进行扩容，当数组元素个数达到阈值时，会触发transfer方法，重新调整节点的位置。
transfer实现
transfer方法实现了在并发的情况下，高效的从原始组数往新数组中移动元素，假设扩容之前节点的分布如下，这里区分蓝色节点和红色节点，是为了后续更好的分析：
在上图中，第14个槽位插入新节点之后，链表元素个数已经达到了8，且数组长度为16，优先通过扩容来缓解链表过长的问题，实现如下：
1、根据当前数组长度n，新建一个两倍长度的数组nextTable；
2、初始化ForwardingNode节点，其中保存了新数组nextTable的引用，在处理完每个槽位的节点之后当做占位节点，表示该槽位已经处理过了；
3、通过for自循环处理每个槽位中的链表元素，默认advace为真，通过CAS设置transferIndex属性值，并初始化i和bound值，i指当前处理的槽位序号，bound指需要处理的槽位边界，先处理槽位15的节点；
4、在当前假设条件下，槽位15中没有节点，则通过CAS插入在第二步中初始化的ForwardingNode节点，用于告诉其它线程该槽位已经处理过了；
5、如果槽位15已经被线程A处理了，那么线程B处理到这个节点时，取到该节点的hash值应该为MOVED，值为-1，则直接跳过，继续处理下一个槽位14的节点；
6、处理槽位14的节点，是一个链表结构，先定义两个变量节点ln和hn，按我的理解应该是lowNode和highNode，分别保存hash值的第X位为0和1的节点，具体实现如下：
使用fn&n可以快速把链表中的元素区分成两类，A类是hash值的第X位为0，B类是hash值的第X位为1，并通过lastRun记录最后需要处理的节点，A类和B类节点可以分散到新数组的槽位14和30中，在原数组的槽位14中，蓝色节点第X为0，红色节点第X为1，把链表拉平显示如下：
1、通过遍历链表，记录runBit和lastRun，分别为1和节点6，所以设置hn为节点6，ln为null；
2、重新遍历链表，以lastRun节点为终止条件，根据第X位的值分别构造ln链表和hn链表：
ln链：和原来链表相比，顺序已经不一样了
hn链：
通过CAS把ln链表设置到新数组的i位置，hn链表设置到i+n的位置；
7、如果该槽位是红黑树结构，则构造树节点lo和hi，遍历红黑树中的节点，同样根据hash&n算法，把节点分为两类，分别插入到lo和hi为头的链表中，根据lo和hi链表中的元素个数分别生成ln和hn节点，其中ln节点的生成逻辑如下：
（1）如果lo链表的元素个数小于等于UNTREEIFY_THRESHOLD，默认为6，则通过untreeify方法把树节点链表转化成普通节点链表；
（2）否则判断hi链表中的元素个数是否等于0：如果等于0，表示lo链表中包含了所有原始节点，则设置原始红黑树给ln，否则根据lo链表重新构造红黑树。
最后，同样的通过CAS把ln设置到新数组的i位置，hn设置到i+n位置。
网友评论
"通过CAS把ln链表设置到新数组的i位置，hn链表设置到i+n的位置；"
这里并没有使用CAS,源码是使用了putObjectVolatile,意思是直接把数据写回主内存
我想问一下，线程B在分配迁移槽的时候并不会分配之前分配过的啊，通过了transferindex， 那么这边理论上不会出现某个线程检测到自己要处理的范围有已经被其他线程处理过的啊？不知道你知道这个条件在什么时候有用？
setTabAt(nextTab, i + n, hn); //高位
还有一点很重要：扩展时每个线程只能修改i或i+n桶位置， 保证了线程互斥，即每个桶位置只能有1个线程修改。 例如现在有16个桶， 需要transfer到32个桶。 每个线程只能修改第0/16, 1/16+1, 2/16+2,.... 或15/16+15位置的桶。
ConcurrentHashMap通过CAS比较桶节点实现线程互斥， 在扩容时可以多线程并发； 但HashMap resize时只能单线程
文中提到达到数组阈值时，会进行扩容。
代码中通过s＞sizeCTL，判断是否进行扩容。
我测试发现，put了两个值（两个值的hash相等），此时数组里只有一个桶有值，并且是个链表。但即使两个值都在一个hash桶里，s却add了两次，变成了2。所以这个阈值到底是数组的阈值，还是node总个数的阈值呢？
可以留一个联系方式吗？
setTabAt(nextTab, i + n, hn); 请教下为什么 这个要将 ln 与后值为0 放入14 ，与后值为1 放入 30这两个位置，这个是后续要做什么处理？ 这块没太get到求教
欢迎订阅《java进阶之路》https://toutiao.io/subjects/85249