ConcurrentHashMap 的实现原理是什么?

数据结构

JDK 7:中 ConcurrentHashMap 采用了数组 + Segment + 分段锁的方式实现。

JDK 8:中 ConcurrentHashMap 参考了 JDK 8 HashMap 的实现,采用了数组 + 链表 + 红黑树的实现方式来设计,内部大量采用 CAS 操作。

ConcurrentHashMap 采用了非常精妙的”分段锁”策略,ConcurrentHashMap 的主干是个 Segment 数组。

final  Segment<K,V>[]  segments;

Segment 继承了 ReentrantLock,所以它就是一种可重入锁(ReentrantLock)。在 ConcurrentHashMap,一个 Segment 就是一个子哈希表,Segment 里维护了一个 HashEntry 数组,并发环境下,对于不同 Segment 的数据进行操作是不用考虑锁竞争的。就按默认的 ConcurrentLevel 为 16 来讲,理论上就允许 16 个线程并发执行。

所以,对于同一个 Segment 的操作才需考虑线程同步,不同的 Segment 则无需考虑。Segment 类似于 HashMap,一个 Segment 维护着一个HashEntry 数组:

transient  volatile  HashEntry<K,V>[]  table;

HashEntry 是目前我们提到的最小的逻辑处理单元了。一个 ConcurrentHashMap 维护一个 Segment 数组,一个 Segment 维护一个 HashEntry 数组。因此,ConcurrentHashMap 定位一个元素的过程需要进行两次 Hash 操作。第一次 Hash 定位到 Segment,第二次 Hash 定位到元素所在的链表的头部。

发表评论