ConcurrentHashMap的实现原理基本都是大厂面试必考内容，而且对于掌握高并发编程也有很大的参考价值，本篇就来详解ConcurrentHashMap的底层实现机制@mikechen

首先，ConcurrentHashMap是HashMap的线程安全版本。

要理解ConcurrentHashMap的实现原理，都会涉及到背后的数据存储：哈希表。

所以，在谈ConcurrentHashMap的实现原理之前，我先从哈希表谈起，然后再循序渐进的谈

ConcurrentHashMap在JDK1.7和1.8之后的详细区别，这样更容易理解ConcurrentHashMap的实现原理@mikechen

01 哈希表

哈希表，英文名为：Hash表，也称散列表，是根据键值而直接进行访问的数据结构。

哈希表它通过把键值（key-value）映射到表中一个位置来访问记录，以加快查找的速度，这个映射函数叫做散列函数，存放记录的数组叫做散列表。

哈希表的数据结构：本质是数组加哈希函数，如下图所示：

key通过哈希函数，得到数组索引位置，然后就可以输出存储，查询也是通过索引来访问数组，所以哈希表的插入和查找的效率非常高，时间复杂度都是O(1)。

哈希表的应用场景

我们熟知的缓存技术，比如redis、memcached等分布式缓存，谈到背后的实现，本质就是：一张巨大的哈希表。

除此之外，还有大家熟知的HashMap、CurrentHashMap等，都是哈希表的应用。

JDK1.7下的CurrentHashMap底层实现

在 JDK 1.7 中，ConcurrentHashMap 的实现原理主要基于分段锁（Segment）的思想。

它将整个哈希表分成了多个小的哈希表段，每个段都对应着一个独立的锁，这样不同的线程可以同时访问不同的哈希表段，从而大大提高了并发性能。

如下图所示：

1.Segment(分段锁)

ConcurrentHashMap中的分段锁称为Segment，它即类似于HashMap的结构，即内部拥有一个Entry数组，数组中的每个元素又是一个链表,同时又是一个ReentrantLock（Segment继承了ReentrantLock）。

2.内部结构

具体来说，ConcurrentHashMap 中的哈希表结构由若干个哈希表段（Segment）组成，每个哈希表段都是一个独立的哈希表，它包含了一个 Entry 数组和一个独立的锁。

每个 Entry 表示一个键值对，其中包含了键、值和一个指向下一个 Entry 的指针。这些哈希表段组成了整个 ConcurrentHashMap 的哈希表结构，每个哈希表段都负责管理一部分键值对。

ConcurrentHashMap定位一个元素的过程需要进行两次Hash操作：

第一次Hash定位到Segment；

第二次Hash定位到元素所在的链表的头部；

3.该结构的优劣势

坏处

这一种结构的带来的副作用是Hash的过程要比普通的HashMap要长

好处

写操作的时候可以只对元素所在的Segment进行加锁即可，不会影响到其他的Segment。

总结：在JDK1.7中ConcurrentHashMap采用了：数组+Segment+分段锁的方式实现。

JDK1.8的CurrentHashMap实现原理

在 JDK 1.8 中，ConcurrentHashMap 的实现原理和 JDK 1.7 中有所不同。

JDK8中彻底放弃了Segment转而采用的是Node，其设计思想也不再是JDK1.7中的分段锁思想。

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

如下图所示：

1.数据结构

取消了Segment分段锁的数据结构，取而代之的是数组+链表+红黑树的结构。

2.保证线程安全机制

JDK1.7采用segment的分段锁机制实现线程安全，JDK1.8采用CAS+Synchronized保证线程安全。

3.链表转化为红黑树

定位结点的hash算法简化会带来弊端,Hash冲突加剧,因此在链表节点数量大于8时，会将链表转化为红黑树进行存储。

4.查询时间复杂度

从原来的遍历链表O(n)，变成遍历红黑树O(logN)。

5.锁的粒度

原来是对需要进行数据操作的Segment加锁，现调整为对每个数组元素加锁，降低了锁的力度。

ConcurrentHashMap避免了对全局加锁改成了局部加锁操作，这样就极大地提高了并发环境下的操作速度。

以上

更多分布式架构系列、阿里架构师进阶系列，请查看以下文章：

阿里架构师进阶从0到1全部合集(建议收藏)