ConcurrentHashMap的实现原理
需积分: 2 166 浏览量
2022-09-07
20:37:20
上传
评论
收藏 17KB DOCX 举报
ConcurrentHashMap 实现原理
在 JDK1.7 中 ConcurrentHashMap 采用了【数组+Segment 分段锁+单向链表】的
方式实现。
1.Segment 分段锁
ConcurrentHashMap 中的分段锁称为 Segment，它即类似于 HashMap 的结构，
即内部拥有一个 Entry 数组，数组中的每个元素又是一个链表，同时又是一个
ReentrantLock（Segment 继承了 ReentrantLock）。
2.内部结构。
ConcurrentHashMap 使用分段锁技术实现线程安全行，将数据分成一段一段
的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的
时 候 ， 其 他 段 的 数 据 也 能 被 其 他 线 程 访 问 ， 能 够 实 现 真 正 的 并 发 访 问 。
ConcurrentHashMap 定位一个元素的过程需要进行两次 Hash 操作。第一次 Hash
定位到 Segment，第二次 Hash 定位到元素所在的链表的头部。
- 坏处：这一种结构的带来的副作用是 Hash 的过程要比普通的 HashMap 要长
- 好处：写操作的时候可以只对元素所在的 Segment 进行加锁即可，不会影响
到其他的 Segment，这样，在最理想的情况下，ConcurrentHashMap 可以最高同
时支持 Segment 数量大小的写操作（刚好这些写操作都非常平均地分布在所有的
Segment 上）。所以通过这种结构，ConcurrentHashMap 的并发能力可以大大的
提高。
* JDK8 中 ConcurrentHashMap 采用了【数组+链表+红黑树】的实现方式来设计，
内部大量采用 CAS 操作。CAS 是 compare and swap 的缩写，即比较交换。CAS 是
一种基于锁的操作，而且是乐观锁。
* JDK8 中彻底放弃了 Segment 转而采用的是 Node，其设计思想也不再是 JDK1.7
中的分段锁思想。
* Node：保存 key，value 及 key 的 hash 值的数据结构。其中 value 和 next 都
用 volatile 修饰，保证并发的可见性。
* 在 JDK8 中 ConcurrentHashMap 的 结 构 ， 由 于 引 入 了 红 黑 树 ， 使 得
ConcurrentHashMap 的实现非常复杂，红黑树是一种性能非常好的二叉查找树，
其查找性能为 O（logN），但是其实现过程也非常复杂，而且可读性也非常差，
早 期 完 全 采 用 链 表 结 构 时 Map 的 查 找 时 间 复 杂 度 为 O （ N ） ， JDK8 中
ConcurrentHashMap 在链表的长度大于某个阈值的时候会将链表转换成红黑树
进一步提高其查找性能。
资源评论
