ConcurrentHashMap 的实现原理 (JDK1.7 和 JDK1.8)

缺乏、安全感 2021-09-21 06:12 309阅读 0赞

HashMap、CurrentHashMap 的实现原理基本都是 BAT 面试必考内容，阿里 P8 架构师谈：深入探讨 HashMap 的底层结构、原理、扩容机制深入谈过 hashmap 的实现原理以及在 JDK 1.8 的实现区别，今天主要谈 CurrentHashMap 的实现原理，以及在 JDK1.7 和 1.8 的区别。

内容目录：1. 哈希表 2.ConcurrentHashMap 与 HashMap、HashTable 的区别 3.CurrentHashMap 在 JDK1.7 和 JDK1.8 版本的区别

![u_1313111989_3569341969_fm_173_app_25_f_JPEG_w_640_h_364_s_D2102A649E745D8E1F287E3A0300D0D0][]

> ### 哈希表 ###

1. 介绍

哈希表就是一种以 键 - 值 (key-indexed) 存储数据的结构，我们只要输入待查找的值即 key，即可查找到其对应的值。

哈希的思路很简单，如果所有的键都是整数，那么就可以使用一个简单的无序数组来实现：将键作为索引，值即为其对应的值，这样就可以快速访问任意键的值。这是对于简单的键的情况，我们将其扩展到可以处理更加复杂的类型的键。

2. 链式哈希表

链式哈希表从根本上说是由一组链表构成。每个链表都可以看做是一个 “桶”，我们将所有的元素通过散列的方式放到具体的不同的桶中。插入元素时，首先将其键传入一个哈希函数（该过程称为哈希键），函数通过散列的方式告知元素属于哪个 “桶”，然后在相应的链表头插入元素。查找或删除元素时，用同们的方式先找到元素的 “桶”，然后遍历相应的链表，直到发现我们想要的元素。因为每个 “桶” 都是一个链表，所以链式哈希表并不限制包含元素的个数。然而，如果表变得太大，它的性能将会降低。

![u_2742330931_2750117589_fm_173_app_25_f_JPEG_w_494_h_274_s_7BA83063F3C349490EDDE1DA000080B1][]

3. 应用场景

我们熟知的缓存技术（比如 redis、memcached）的核心其实就是在内存中维护一张巨大的哈希表，还有大家熟知的 HashMap、CurrentHashMap 等的应用。

> #### ConcurrentHashMap 与 HashMap 以及HashTabl等的区别 ####

1.HashMap

我们知道 HashMap 是线程不安全的，在多线程环境下，使用 Hashmap 进行 put 操作会引起死循环，导致 CPU 利用率接近 100%，所以在并发情况下不能使用 HashMap。

2.HashTable

HashTable 和 HashMap 的实现原理几乎一样，差别无非是

HashTable 不允许 key 和 value 为 null HashTable 是线程安全的但是 HashTable 线程安全的策略实现代价却太大了，简单粗暴，get/put 所有相关操作都是 synchronized 的，这相当于给整个哈希表加了一把大锁。

多线程访问时候，只要有一个线程访问或操作该对象，那其他线程只能阻塞，相当于将所有的操作串行化，在竞争激烈的并发场景中性能就会非常差。

3.ConcurrentHashMap

主要就是为了应对 hashmap 在并发环境下不安全而诞生的，**ConcurrentHashMap 的设计与实现非常精巧，大量的利用了 volatile，final，CAS 等 lock-free 技术来减少锁竞争对于性能的影响**。

我们都知道 Map 一般都是数组 + 链表结构（JDK1.8 该为数组 + 红黑树）。

![u_3287879701_227201483_fm_173_app_25_f_JPEG_w_405_h_281_s_4393EB22FB37408A08C425DA0200C0B2][]

ConcurrentHashMap 避免了对全局加锁改成了局部加锁操作，这样就极大地提高了并发环境下的操作速度，由于 ConcurrentHashMap 在 JDK1.7 和 1.8 中的实现非常不同，接下来我们谈谈 JDK 在 1.7 和 1.8 中的区别。

> ### JDK1.7 版本的 CurrentHashMap 的实现原理 ###

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

1.Segment (分段锁)

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

2. 内部结构

ConcurrentHashMap 使用分段锁技术，将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问，能够实现真正的并发访问。如下图是 ConcurrentHashMap 的内部结构图：

![u_1123993683_437526452_fm_173_app_25_f_JPEG_w_640_h_341_s_5AA834639B9759CA0CF5E1DF0000C0B1][]

从上面的结构我们可以了解到，ConcurrentHashMap 定位一个元素的过程需要进行两次 Hash 操作。

**第一次 Hash 定位到 Segment，第二次 Hash 定位到元素所在的链表的头部**。

3. 该结构的优劣势

坏处

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

好处

写操作的时候可以只对元素所在的 Segment 进行加锁即可，不会影响到其他的 Segment，这样，在最理想的情况下，ConcurrentHashMap 可以最高同时支持 Segment 数量大小的写操作（刚好这些写操作都非常平均地分布在所有的 Segment 上）。

所以，通过这一种结构，ConcurrentHashMap 的并发能力可以大大的提高。

> ### JDK1.8 版本的 CurrentHashMap 的实现原理 ###

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

CAS 是 compare and swap 的缩写，即我们所说的比较交换。cas 是一种基于锁的操作，而且是乐观锁。在 java 中锁分为乐观锁和悲观锁。悲观锁是将资源锁住，等一个之前获得锁的线程释放锁之后，下一个线程才可以访问。而乐观锁采取了一种宽泛的态度，通过某种方式不加锁来处理资源，比如通过给记录加 version 来获取数据，性能较悲观锁有很大的提高。

CAS 操作包含三个操作数 —— 内存位置（V）、预期原值（A）和新值 (B)。如果内存地址里面的值和 A 的值是一样的，那么就将内存里面的值更新成 B。CAS 是通过无限循环来获取数据的，若果在第一轮循环中，a 线程获取地址里面的值被 b 线程修改了，那么 a 线程需要自旋，到下次循环才有可能机会执行。

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

Node：保存 key，value 及 key 的 hash 值的数据结构。其中 value 和 next 都用 volatile 修饰，保证并发的可见性。

Java8 ConcurrentHashMap 结构基本上和 Java8 的 HashMap 一样，不过保证线程安全性。

在 JDK8 中 ConcurrentHashMap 的结构，由于引入了红黑树，使得 ConcurrentHashMap 的实现非常复杂，我们都知道，红黑树是一种性能非常好的二叉查找树，其查找性能为 O（logN），但是其实现过程也非常复杂，而且可读性也非常差，DougLea 的思维能力确实不是一般人能比的，早期完全采用链表结构时 Map 的查找时间复杂度为 O（N），JDK8 中 ConcurrentHashMap 在链表的长度大于某个阈值的时候会将链表转换成红黑树进一步提高其查找性能。

![u_1897711906_4275469846_fm_173_app_25_f_JPEG_w_640_h_316_s_4CAE38728482D6A242FC58C600007022][]

总结

其实可以看出 JDK1.8 版本的 ConcurrentHashMap 的数据结构已经接近 HashMap，相对而言，ConcurrentHashMap 只是增加了同步的操作来控制并发，从 JDK1.7 版本的 ReentrantLock+Segment+HashEntry，到 JDK1.8 版本中 synchronized+CAS+HashEntry + 红黑树。

1.  数据结构：取消了 Segment 分段锁的数据结构，取而代之的是数组 + 链表 + 红黑树的结构。
2.  保证线程安全机制：JDK1.7 采用 segment 的分段锁机制实现线程安全，其中 segment 继承自 ReentrantLock。**JDK1.8 采用 CAS+Synchronized 保证线程安全**。
3.  锁的粒度：原来是对需要进行数据操作的 Segment 加锁，现调整为对每个数组元素加锁（Node）。
4.  链表转化为红黑树：**定位结点的 hash 算法简化会带来弊端，Hash 冲突加剧，因此在链表节点数量大于 8 时，会将链表转化为红黑树进行存储**。
5.  查询时间复杂度：从原来的遍历链表 O (n)，变成遍历红黑树 O (logN)。

> ### 关于JDK1.7和1.8的总结 ###

**ConcurrentHash使用ReentrantLock（JDK1.7），或者CAS结合synchronized（JDK1.8）来**实现线程安全，可以支持多个线程同时进行读写操作，提高并发读写的性能。

**（一）JDK1.7**

**1.put写操作**

首先通过key的hash确定segments数组的下标，即需要往哪个segment存放数据。确定好segment之后，则调用该segment的put方法，写到该segment内部的哈希表table数组的某个链表中，链表的确定也是根据key的hash值和segment内部table大小取模。

*  在ConcurrentHashMap中的put操作是没有加锁的，**而在Segment中的put操作，通过ReentrantLock加锁**
 *  Segment类的put操作定义：首先获取lock锁，然后根据key的hash值，获取在segment内部的HashEntry数组table的下标，从而获取对应的链表，具体为链表头。

**2.get读操作**

*  获取指定的key对应的value，get读操作是不用获取lock锁的，即不加锁的，**通过使用UNSAFE的volatile版本的方法保证线程可见性。**

**3.size容量计算**

*  size方法主要是计算当前hashmap中存放的元素的总个数，即累加各个segments的内部的哈希表table数组内的所有链表的所有链表节点的个数。
 *  实现逻辑为：**整个计算过程刚开始是不对segments加锁的，重复计算两次**，如果前后两次hashmap都没有修改过，则直接返回计算结果，如果修改过了，则再加锁计算一次。

**（二）JDK1.8**

**1.put写操作**

写操作主要在putVal方法定义，实现逻辑与HashMap的putVal基本一致，只是相关操作，**如获取链表节点，更新链表节点的值value和新增链表节点，都会使用到UNSAFE提供的硬件级别的原子操作**，而如果是**更新链表节点的值或者在一个已经存在的链表中新增节点**，则是**通过synchronized同步**锁来实现线程安全性。

*  如果当前需要put的key**对应的链表在哈希表table中还不存在**，即还没添加过该key的hash值对应的链表，则调用**UNSAFE的casTabAt方法**，**基于CAS机制**来实现添加该链表头结点到哈希表table中，避免该线程在添加该链表头结的时候，其他线程也在添加的并发问题；如果CAS失败，则进行自旋，通过继续第2步的操作；
 *  **如果需要添加的链表已经存在哈希表table中**，则通过UNSAFE的tabAt方法，基于volatile机制，获取当前最新的链表头结点f，由于f指向的是ConcurrentHashMap的哈希表table的某条链表的头结点，故虽然f是临时变量，由于是引用共享的该链表头结点，所以可以**使用synchronized关键字来同步多个线程对该链表的访问**。在synchronized(f)同步块里面，则是与HashMap一样遍历该链表，如果该key对应的链表节点已经存在，则更新，否则在链表的末尾新增该key对应的链表节点。

使用synchronized同步锁的原因：

*  因为如果该key对应的节点所在的链表已经存在的情况下，可以通过UNSAFE的tabAt方法基于volatile获取到该链表最新的头节点，但是**需要通过遍历该链表来判断该节点是否存在，如果不使用synchronized对链表头结点进行加锁，则在遍历过程中，其他线程可能会添加这个节点**，导致重复添加的并发问题。故通过synchronized锁住链表头结点的方式，保证任何时候只存在一个线程对该链表进行更新操作。

**2.get读操作**

*  get读操作由于是从哈希表中查找并读取链表节点数据，不会对链表进行写更新操作，故基于**volatile的happend-before原则保证的线程可见性**（即一个线程的操作对其他线程可见），即可保证get读取到该key对应的最新链表节点，**整个过程不需要进行加锁**。

**3.size容量计算**

*  size方法为计算当前ConcurrentHashMap一共存在多少链表节点，与JDK1.7中每次需要遍历segments数组来计算不同的是，在JDK1.8中，使用baseCount和counterCells数组，在增删链表节点时，实时更新来统计，在size方法中直接返回即可。整个过程不需要加锁。
 *  并发修改异常处理：CounterCell的value值为1，作用是某个线程在更新baseCount时，如果存在其他线程同时在更新，则放弃更新baseCount的值，即保持baseCount不变，而是各自往counterCells数组添加一个counterCell元素，在size方法中，累加counterCells数组的value，然后与baseCount相加，从而获取准确的大小。

**简而言之：**

在设计中，使用了分而治之的思想，将每一个计数都分散到各个 countCell 对象里面（下面称之为桶），使竞争最小化，又使用了 CAS 操作，就算有竞争，也可以对失败了的线程进行其他的处理。

*  先利用 CAS 递增 Count 值来感知是否存在线程竞争，若竞争不大直接 CAS 递增 Count 值即可，性能与直接 Count++ 差别不大
 *  如果有 线程竞争，则 CAS 失败，则初始化桶，利用桶计数，此时是分而治之的思想来计数，同时使用 CAS 来计数，最大化利用并行。如果桶计数频繁失败，则扩容桶。

**（三）补充**

**1.java中的unsafe类**

CAS 并发原语现在 Java 语言中就是 Unsafe 类的各个方法，调用 Unsafe 类中的 CAS 方法，JVM 会帮我们实现 CAS 汇编指令，这是一种完全依赖硬件的功能，通过它实现了原子操作，由于 CAS 是一种系统原语，原语属于操作系统用语范畴，是由于诺干条指令组成的，用于完成某个功能的一个过程，并且原语的执行必须是连续的，在执行过程中不允许被中断，也就是说 CAS 是一条 CPU 原子指令，不会造成所谓的数据不一致问题。

[u_1313111989_3569341969_fm_173_app_25_f_JPEG_w_640_h_364_s_D2102A649E745D8E1F287E3A0300D0D0]: /images/20210920/413895cd347246c6b81c3ee1445dfa54.png
[u_2742330931_2750117589_fm_173_app_25_f_JPEG_w_494_h_274_s_7BA83063F3C349490EDDE1DA000080B1]: /images/20210920/57c7757b3fef4bb68a95c8a60aac7d80.png
[u_3287879701_227201483_fm_173_app_25_f_JPEG_w_405_h_281_s_4393EB22FB37408A08C425DA0200C0B2]: /images/20210920/63a3a7c6c2d549eaaa9f3c3fd1b02f1e.png
[u_1123993683_437526452_fm_173_app_25_f_JPEG_w_640_h_341_s_5AA834639B9759CA0CF5E1DF0000C0B1]: /images/20210920/ce0eb5336022406c97f2215d3e1d7edd.png
[u_1897711906_4275469846_fm_173_app_25_f_JPEG_w_640_h_316_s_4CAE38728482D6A242FC58C600007022]: /images/20210920/257e399ae1f94d14a0e4fceca7e46fe8.png