ConcurrentHashMap

sizeCtl：创建ConcurrentHashMap对象时为容器的指定大小处理后的值或者默认值
sizeCtl：初始化数组时为-1，表示正在初始化

使用ConcurrentHashMap最长用的也应该是put和get方法

put方法

• 1、计算key的hash值
• 2、如果元素数组为null，未初始化，先初始化数组
• 3、否则如果通过hash值索引到位置的元素为null，则直接通过CAS操作插入到索引位置，成功直接返回
• 4、否则如果当前key的hash值索引到的位置的元素的hash值为-1（MOVE，特殊节点），
• 5、否则，出现了hash冲突，通过链地址法处理hash冲突。

1、计算hash值

int hash = spread(key.hashCode());

image.png

• 获取key的hashcode
• 高16位和低16位按位异或运算，这样做为了使hash更均匀

2、初始化数组

image.png

• 将sizeCtl的值赋值给sc，并判断sc（即sizeCtl）是否小于0；
• 如果小于0，当前线程让出CPU，保证只有一个线程能够进行初始化操作
• 否则如果通过CAS操作将sizeCtl的值设置为-1成功，创建初始化的数组对象，并将当前数组大小的四分之三的值赋值给sizeCtl，（因为n为2的倍数，所以n >>> 2就是n/4，所以 n - (n >>> 2)为n的四分之三）
• 可以看出初始化数组时，能够进行初始化的线程会将sizeCtl的值通过CAS操作设置为-1

5、解决hash冲突

image.png

• 链表节点（当前Node f的hash值大于0（fh >= 0））

  • 锁住当前头节点，重新获取索引位置的头节点如果等于锁住的节点
  • 如果fh（节点hash值）大于零，遍历头节点关联的链表，找到hash值相同和key相同的节点，直接替换掉老的value即可；当遍历到链表的尾节点时（节点的next指向null），直接修改当前尾节点next指向新添加的几点即可。

• 树节点（f instanceof TreeBin）

  • 如果当前节点时树节点，走树化解决冲突的逻辑

• 链表树化

  • 最后根据链表节点的长度是否大于等于8，决定是否将链表存储转化成红黑树存储