首页 > 编程学习 > 基础--Concurrenthashmap的实现原理分析

基础--Concurrenthashmap的实现原理分析

发布时间:2022/11/8 22:22:39

一、为什么用ConcurrentHashMap?

        ConcurrentHashMap线程安全且高效的操作,如下图对比所示。而HashMap非线程安全,在put操作时,易出现死循环,即:链表会形成环形(next元素指向前一个元素)

jdk1.7中采用Segment[] + HashEntry的方式进行实现

对于segment片段的理解

Segment是一种可重入锁(ReentrantLock:是一种过程可以多次声明该锁而不会对其自身进行阻塞的锁),在ConcurrentHashMap里扮演锁的角色 

ConcurrentHashMap初始化时,计算出Segment数组的大小size和每个Segment中HashEntry数组的大小cap,并初始化Segment数组的第一个元素;其中size大小为2的幂次方,默认为16,cap大小也是2的幂次方,最小值为2,最终结果根据根据初始化容量initialCapacity进行计算,其中Segment在实现上继承了ReentrantLock,这样就自带了锁的功能。

当执行put方法插入数据时,根据key的hash值,在Segment数组中找到相应的位置,如果相应位置的Segment还未初始化,则通过CAS进行赋值,接着执行Segment对象的put方法通过加锁机制插入数据。

1、线程A执行tryLock()方法成功获取锁,则把HashEntry对象插入到相应的位置;
2、线程B获取锁失败,则执行scanAndLockForPut()方法,在scanAndLockForPut方法中,会通过重复执行tryLock()方法尝试获取锁,在多处理器环境下,重复次数为64,单处理器重复次数为1,当执行tryLock()方法的次数超过上限时,则执行lock()方法挂起线程B;

3、当线程A执行完插入操作时,会通过unlock()方法释放锁,接着唤醒线程B继续执行;

size实现
因为ConcurrentHashMap是可以并发插入数据的,所以在准确计算元素时存在一定的难度,一般的思路是统计每个Segment对象中的元素个数,然后进行累加,但是这种方式计算出来的结果并不一样的准确的,因为在计算后面几个Segment的元素个数时,已经计算过的Segment同时可能有数据的插入或则删除,在1.7的实现中,采用了如下方式:

先采用不加锁的方式,连续计算元素的个数,最多计算3次: 
1、如果前后两次计算结果相同,则说明计算出来的元素个数是准确的; 
2、如果前后两次计算结果都不同,则给每个 Segment 进行加锁,再计算一次元素的个数; 

1.8实现

设计:Node对象+synchronized+CAS的设计方式来保证并发安全。
ConcurrentHashMap在1.8中的实现,相比于1.7的版本基本上全部都变掉了。首先,取消了Segment分段锁的数据结构,取而代之的是数组+链表(红黑树)的结构。而对于锁的粒度,调整为对每个数组元素加锁(Node)。然后是定位节点的hash算法被简化了,这样带来的弊端是Hash冲突会加剧。因此在链表节点数量大于8时,会将链表转化为红黑树进行存储。这样一来,查询的时间复杂度就会由原先的O(n)变为O(logN)。下面是其基本结构:
  


1.8中放弃了Segment臃肿的设计,取而代之的是采用Node + CAS + Synchronized来保证并发安全进行实现,

只有在执行第一次put方法时才会调用initTable()初始化Node数组,实现如下

总结1.8:

1.结构:Node数组 + 链表/红黑树的结构 .数组某下标位置对应的链表元素突破8个以后,转变为红黑树。红黑树元素小于6个变回成链表。

TREEIFY_THRESHOLD=8 ;UNTREEIFY_THRESHOLD = 6;这里需要注意,不是元素小于6的时候一定会变成链表,只有resize的时候才会根据UNTREEIFY_THRESHOLD 进行转换,同样也不是到8的时候就变成红黑树(不是等到扩容的时候) 链表与红黑树的转换详情)

2.其线程安全都是使用volatile修饰且自旋CAS操作

3.HashMap线程不安全
在put的时候,Resize(扩容)会造成数据的覆盖
JDK1.7 因为是头插法,可能会造成循环链表
JDK1.8 是尾插法

参考:

ConcurrentHashMap的实现原理_爱我所爱0505的博客-CSDN博客_concurrenthashmap的实现原理

Copyright © 2010-2022 dgrt.cn 版权所有 |关于我们| 联系方式