concurrentHashMap 1.8笔记

本文主要对JDK1.8版本的ConcurrentHashMap的主要流程做简要记录，并对主要的位运算做简要分析。源码分析可以参考如下大佬们的详细分析：
ZOKEKAI：ConcurrentHashMap1.8 - 扩容详解
编程芝士：ConcurrentHashMap底层详解(图解扩容)（JDK1.8）

复习：

        int aa = 32;       //0b00000000_00000000_00000000_00100000
        int a0 = -32;      //0b11111111_11111111_11111111_11100000  负数表示为补码，最左符号位不变，其余按上面正数的位取反11111111_11111111_11111111_11011111 补码+1 变为11111111_11111111_11111111_11100000
        int a1 = -32 >> 2; //0b11111111_11111111_11111111_11111000  符号位不位移
        int a2 = -32 >>>2; //0b00111111_11111111_11111111_11111000  符号位位移，右侧溢出，高位补0
        int a3 = -32 >>>6; //0b00000011_11111111_11111111_11111111  符号位位移，右侧溢出，高位补0
        int a4 = -32 >>>8; //0b00000000_11111111_11111111_11111111  符号位位移，右侧溢出，高位补0
        int a5 = -32 << 2;
//        int a6 = -32 <<< 2;没有带符号位右移

1、put流程

• 判断是否为空，concurrentHashmap键值对都不能为空

• 通过spread（）计算hash；hashcode - > h (h ^ (h >>> 16)) & HASH_BITS;

• 如果

  • map对象的table数组Node[]为空，初始化创建table数组initTable()

  • table不为空，则通过 i = (n - 1) & hash 计算索引从table找对应node节点，如果对应node节点为null,则通过casTabAt方法以CAS自旋的方式往该索引位置添加节点

  • 如果通过索引 i 获取的node节点 f 不为null,且f.hash == MOVED == -1 ，（也就是这个节点是forwordingNode）表示某个线程正在对当前map对象的table扩容，当前线程需要通过helpTransfer（）方法协助扩容

  • node不为空，且没有其他线程在做迁移，对链表(红黑树)中的根节点 f 加了synchronized 锁。

     根节点 f 的哈希值，如果这个值大于等于0就代表是链表，否则就是红黑树。
     如果是链表的话，就循环的比较与当前链表中每个节点的hash值和equals是否相等，
     相等的话就覆盖，不相等的话就在链表的尾部插入新的节点
     
     如果 f 是红黑树 ，那么就是已经树化了，数据的插入就是红黑树的插入。
     要注意的是，这里是红黑树的话 f 是一个TreeBin 对象而不直接是红黑树的根节点,
     因为在红黑树的插入 *** 作时有可能红黑树的根节点发生变化。
     如果对红黑树的根节点进行加锁，put之后根节点发生了变化，
     其他线程获得这个就可以获得新节点并加锁，这样就会出错。
     如果是TreeBin 对象的话，锁住的就是这个对象，根节点发生变化不会影响加锁。
    

• 插入新节点后，判断链表是否大于8，大于8则进入treeifyBin（）方法将链表升级为红黑树。treeifyBin（）方法中会先判断是否node数组长度低于64 MIN_TREEIFY_CAPACITY，低于MIN_TREEIFY_CAPACITY的话会先尝试 tryPresize（）扩容。

• put完成后，在addCount方法中计数存储量+1，并判断是否需要扩容。

2、initTable()

• 判断sizeCtl的值，如果该值小于0，表明已经有其他的线程初始化了（sizectl == -1）,或者其他负数，正在扩容，则当前线程让出CPU时间Thread.yield();
• 初始化时，当前线程通过CAS修改sizeCtl为-1，修改成功的话，开始创建table，
• 将sizeCtl 设置为n - (n >>> 2);即触发扩容的阈值。n >>>2 即n / 4,则n - (n >>> 2) == 75% * n。即达到容量的75%触发扩容。

3、addCount（）

• 先判断countCeil数组是否为空，为空的话直接通过CAS修改baseCount。
• 如果CAS执行失败，表明有竞争，初始化countCeil数组，采用与longaddr一样的原理，分别计算最后加总的方式计数

4、扩容

触发扩容动作：

• put()方法中，某个node 链表长度到达8 ，但node数组长度还没有超过64,超过64则将链表转成红黑树
• addCount（）方法中数组元素个数到达阈值 75% * n
• 其他线程在对map进行插入，修改，删除，合并，compute *** 作时遇到ForwardingNode
  会触发协助扩容helpTransfer（）转移node。
  get *** 作时，通过ForwardingNode转移到新的node数组访问对应的node。

resizeStamp() 在扩容中有个方法生成当次扩容唯一标识，

(1 << (RESIZE_STAMP_BITS - 1)即是1<<15，表示为二进制即是高16位为0，第16位为1；

• eg: 当容量n=16
  resizeStamp的值为0000000_00000000_10000000_00011011,因为扩容都是2的N次幂，因此每次扩容时的capacity在二进制中的1的位置都不一样，resizeStamp的低16位表示capacity在二进制中的1的位置左侧还有多少个0（可认为是标识此次扩容前的容量），因此resizeStamp可以唯一标识当次扩容。

resizeStamp(int n) {
        return Integer.numberOfLeadingZeros(n) | (1 << (RESIZE_STAMP_BITS - 1));
}

resizeStamp值的作用：

当sizeCtl >= 0时； 标识没有线程在扩容，当前线程通过CAS将sizeCtl修改为
(rs < 当n=16时, resizeStamp的值为0000000_00000000_10000000_00011011
那么rs << RESIZE_STAMP_SHIFT) + 2为：10000000_00011011_0000000_00000010
此时sizeCtl<0; 那么sizeCtl 高16位可认为是代表容量，每次扩容唯一。低16位的值等于参与扩容的线程数+1 。当sizeCtl < 0时；其他线程进来时判断sizeCtl< 0；说明已经有线程在执行扩容，那么当前线程通过CAS对sizeCtl+1，并协助扩容。

transfer() 扩容

一、任务分配。

• 1、计算每个线程需要处理的node节点个数Stride，每个线程处理的node节点数量一样，一个线程最少负责16个node节点。
• 2、初始时transferIndex为node数组长度，即容量n;Stride为每个线程此次需要迁移的node节点数。i为当前迁移任务的的开始下标，bound为此次迁移任务的结束下标。
• 3、第一个线程A领取任务，假设stride==16，transferIndex = transferIndex -bound，线程A处理i(A)-bound(A)的node节点迁移。
• 4、当其他线程参与协助转移，按同样的方式分配i-bound的处理范围。同时sizeCtl + 1;

二、链表或者红黑树迁移

• 普通链表迁移
  

  • 1、首先锁住索引i对应的node节点，对当前node节点链表遍历，查找lastRun节点，当某个节点是lastRun，那么lastrun节点后续的链表节点都属于跟lastrun同类型（hn或者ln）的节点
  • 2、ln节点hn节点判断方法：

int b = p.hash & n; 假设n = 8 0000_1000 记值为1的位为runbit为3
hash1 = 7, 0000_0111 & 0000_1000 -> runbit位值为0
hash2 = 15, 0000_1111 & 0000_1000 -> runbit 位值为1
hash3 = 23, 0001_0111 & 0000_1000 -> runbit 位值为0
即runbit 位为1时，肯定是余数+奇数倍的n,为0时，肯定是余数+偶数倍的n
以上三个hash的 mod 8均取余数 m = 7 (或 hash &（n-1）)
即hash = a*n + m ;
a为偶数时，hash & n 的runbit位为0，记为低位节点hash
a为奇数时，hash & n 的runbit位为1，记为高位节点hash
扩容后，n<<2 为16，0001_0000
低位节点hash mod 16,与扩容前 hash mod 8 两者取余 m 相等 高位节点hash mod16,扩容后取余 等于 m + 8(即 m + 扩大的容量n)

• • 3、将lastrun节点（假设为高位节点）及后续节点作为hn的初始链表（lastrun为高位节点，则为hn链表，否则为ln链表）将原始链表中，其余同类型节点，从前往后取出复制头插入到到新的hn链表
  • 4、将lastrun节点前一个节点必定为ln类型的节点，其作为ln的初始节点。然后按同样的方式构建链表
  • 5、将ln链表迁移到新node数组的索引 i位置，将hn链表迁移到新node数组i+n 位置。
  • 6、迁移完成后将该node节点设置为fwd节点ForwardingNode，表示迁移完毕

红黑树迁移：

• 1、首先锁住索引 i 对应的node节点（treebin节点）。
• 2、遍历整个红黑树，用尾插构建ln和hn链表
• 3、如果新的链表不满足红黑树条件，则按链表方式迁移到新的node数组对应索引位置，如果满足红黑树条件，则以红黑树的结构迁移到新的node数组的对应索引位置
• 4、迁移完成后将该node节点设置为fwd节点ForwardingNode，表示迁移完毕

三、任务结束

• 每个线程执行完成一个任务后，将sizeCtl -1，如果该线程在领取新的任务，则sizeCtl 再+1；
  迁移完成后，sizeCtl 设置为2*n * 75%,即新的容量的75%。sizeCtl = (n << 1) - (n >>> 1);

四、当正在发生扩容迁移时，如果存取

• 1、存取未发生迁移的node节点的数据，正常进行get和put *** 作
• 2、get *** 作遇到fwd节点（已经迁移完毕的节点）时，转发到新的node数组查找
• 3、put *** 作遇到fwd节点时，开始协助转移node节点
• 4、当get的节点正在发生迁移，由于迁移都是复制 *** 作，所以get访问依旧可以在旧的node数组访问
• 5、当put的节点正在发生迁移，由于正在迁移的node已经加锁了，所以，put *** 作会阻塞。