一图相识ConcurrentHashMap底层原理

手机游戏开发者 · 2024-9-17 17:07:03

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的话，则转为单向链表，挂在数组上

一图相识ConcurrentHashMap底层原理

所属分类: 问答交流

新帖推荐: 30日

推荐作品