Question

一图了解ConcurrentHashMap底层原理

Answer 1

1、ConcurrentHashMap底层数据结构是一个数组table
2、table数组上挂着单向链表或红黑树
3、new ConcurrentHashMap();如果没有指定长度的话，默认是16，并且数组长度必须是2的n次幂，若自定义初始化的长度不是2的n次幂，那么在初始化数组时，会吧数组长度设置为大于自定义长度的最近的2的n次幂。（如：自定义长度为7，那么实际初始化数组后的长度为8）
4、底层是使用synchronized作为同步锁，并且锁的粒度是数组的具体索引位（有些人称之为分段锁）。
5、Node节点，hash>0，当hash冲突时，会形成一个单向链表挂在数组上。
6、ForwardindNode，继承至Node，其hash=-1，表示当前索引位的数据已经被迁移到新数组上了
7、ReservationNode，继承至Node，其hash=-3，表示当前索引位被占用了（compute方法）
8、TreenBin，继承至Node，其hash=-2，代表当前索引下挂着一颗红黑树
9、lockState为ConcurrentHashMap底层自己实现的基于cas的读写锁，锁粒度是具体的某颗树。当向红黑树进行增，删操作时，首先会先上sync同步锁，然后自平衡的时候会上lockState写锁，当读红黑树的时候，会上lockState读锁，然后判断此时是否有线程正持有写锁，或是否有线程正在等待获取写锁，若有，则读线程会直接去读双向链表，而不是去读红黑树。
10、TreeNode，hash>0，为红黑树具体节点。TreeBin的root代表红黑树的根节点，first代表双向链表的第一个节点
11、双向链表：构建红黑树时还维护了一个双向链表，其目的为：(1)当并发写读同一颗红黑树的时候，读线程判断到有线程正持有写锁，那么会跑去读取双向链表，避免因为并发写读导致读线程等待或阻塞。(2)当扩容的时候，会去遍历双向链表，重新计算节点hash，根据新的hash判断放在新数组的高位还是地位

1、触发扩容的规则：
1）添加完元素后，若判断到当前容器元素个数达到了扩容的阈值（数组长度*0.75），则会触发扩容
2）添加完元素后，所在的单向链表长度>=8，则会转为红黑树，不过在转红黑树之前会判断数组长度是否小于64，若小于64则会触发扩容
2、table为扩容前的数组，nextTable为扩容中创建的新数组，迁移数据完毕后需要将nextTable赋值给table
3、扩容后的数组是元素组长度的2倍
4、ln，hn分别表示高位和低位的链表（高链，低链）。即，扩容时，会用n&h==0来判断元素应该放在新数组的i位置还是i+n位置。n：元素组长度；h：元素hash值；i：元素所在的原数组索引位；。这样就会出现有些元素会被挂在低位，有些元素会被挂在高位，从而达到打散元素的目的。
5、红黑树扩容时，会遍历双向链表，并且计算n&h==0来判断元素放在低位（lo）还是高位（ho），确定完元素的去处之后，会判断分别判断两个双向链表（lo,ho）的长度是否大于6，若大于6则将还是以一颗红黑树的结构挂在数组上，若<=6的话，则转为单向链表，挂在数组上