关于chm扩容结束的判断条件思考

jdk中存在的并发安全的map集合ConcurrentHashMap,它可以实现多线程并发扩容,理论上最大并发粒度为((1<<16) -1). 关于并发扩容的原理不是本文的研究重点.本文只讨论jdk1.8版本下的ConcurrentHashMap的扩容结束条件.

int rs = resizeStamp(n);if (sc < 0) {    if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||        sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||        transferIndex <= 0)        break;复制代码

1. (sc >>> RESIZE_STAMP_SHIFT) != rs
2. sc == rs + 1
3. sc == rs + MAX_RESIZERS
4. (nt = nextTable)==null
5. transferIndex <= 0

(nt = nextTable) == null

if (finishing) {    nextTable = null;    table = nextTab;    sizeCtl = (n << 1) - (n >>> 1);    return;}复制代码

结合以上代码分析而言,扩容完成后nextTab=null;

transferIndex<=0

transferIndex代表多个线程对原始数组进行迁移的区间划分.当所有区间划分完成时transferIndex=0,那么后续的线程无法参与扩容.

扩容戳值发生变化

static final int resizeStamp(int n) {    return Integer.numberOfLeadingZeros(n) | (1 << (RESIZE_STAMP_BITS - 1));}RESIZE_STAMP_BITS=16复制代码

resizeStamp方法实际上是根据当前数组长度n生成一个扩容有关的扩容戳,Integer.numberOfLeadingZeros(n)返回无符号整数n最高位非0位前面的0的个数,比如16这个数字的二进制0000 0000 0000 0000 0000 0000 0001 0000,那么返回的值为27.而 1 << (RESIZE_STAMP_BITS - 1)值为1000 0000 0000 0000,这个值得目的是为了保证低16位的值始终是1,因为在后续进行无符号左移16位后低16位变为高16位,最高位位1,其值为负数.

而对于数组长度而言始终为2的n次幂,若最小值为16,那么后续的值必定大于16,进而Integer.numberOfLeadingZeros(n)计算出的值就越小,那么其区间必定在[30,0).与1000 0000 0000 0000进行|运算后,高16位始终为0,也就是说经过后续的左移16位后,低16位的最小值为2.

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

• RESIZE_STAMP_SHIFT=16
• rs为resizeStamp计算后的值

也就是说每个长度的数组,其resizeStamp方法计算出的值都不一样,那么如何前一个线程对数组长度为16的集合进行扩容时,后一个线程发生扩容戳不一致,那么说明前一个线程扩容完毕,因为前一个线程只有在扩容完成时才会改变数组长度.

if (finishing) {    nextTable = null;    table = nextTab;    sizeCtl = (n << 1) - (n >>> 1);    return;}

永不成立的等式

针对 sc == rs + 1和sc == rs + MAX_RESIZERS这两个条件,本人研究了好久始终无法证明这2个条件能成立,因为一旦触发扩容sc必定小于0,而rs又必定大于0,那么这2个条件就无法满足.最后我得出一个结论: 这会不会是jdk1.8的bug呢.于是抱着试一试的心态我到jdk1.8的bug里面找到了相关信息: bugs.java.com/bugdatabase…

sc == rs + 1 应该被替换为sc ==(rs << RESIZE_STAMP_SHIFT) + 1 它的含义是:当前扩容的线程数为0，即已经扩容完成了，就不需要再新增线程扩容

sc == rs + MAX_RESIZERS 应该被替换为sc == (rs << RESIZE_STAMP_SHIFT) + MAX_RESIZERS.它的含义是参与扩容的线程数已经到了最大，就不需要再新增线程扩容

结语: 敢于质疑权威,而不是唯唯诺诺.

作者：遇见阳光
链接：https://juejin.cn/post/7127086034399002654