详解ConcurrentHashMap底层实现机制：大厂面试必考的高并发编程技巧

关注△mikechen的互联网架构△，10年+BAT架构经验。

大家好，我是mikechen|陈锐.

ConcurrentHashMap的实现原理基本上是各大厂商面试的必考，对于掌握高并发编程也有很大的参考价值。本文将详细讲解ConcurrentHashMap的底层实现机制@mikechen

01 哈希表 1.简介

哈希表是一种以键索引格式存储数据的结构。我们只需要输入要查找的值，也就是键，就可以找到对应的值。

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

2. 链式哈希表

链接哈希表基本上由一组链接列表组成。每个链表都可以看作一个“桶”，我们通过哈希将所有元素放入不同的特定桶中。

插入元素时，首先将其键传递给哈希函数（此过程称为哈希键）。函数通过哈希告诉元素属于哪个“桶”，然后将该元素插入到对应链表的头部。

在查找或删除元素时，我们首先用同样的方式找到该元素的“桶”，然后遍历对应的链表，直到找到我们想要的元素。

3、应用场景

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

02 CurrentHashMap和HashMap的区别等1.HashMap

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

2.哈希表

HashTable和HashMap的实现原理几乎是一样的。两者的区别在于：

但HashTable线程安全策略的实现成本太高，而且简单粗暴，所有get/put相关操作都是同步的，相当于给整个哈希表加了一把大锁。

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

3.ConcurrentHashMap

它的诞生主要是为了解决并发环境下HashMap的不安全问题。

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

ConcurrentHashMap避免了全局锁定，改为本地锁定操作，大大提高了并发环境下的操作速度。由于JDK1.7和1.8中ConcurrentHashMap的实现有很大不同，所以我们先来说说JDK 1.7和1.8的区别。

03 JDK1.7下CurrentHashMap实现

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

1.Segment（段锁）

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

2、内部结构

ConcurrentHashMap采用分段锁技术，将数据分成段进行存储，然后为每段数据分配一个锁。当一个线程占用锁访问一段数据时，其他段的数据也可以被其他线程访问。实现真正的并发访问。下图是ConcurrentHashMap的内部结构图：

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

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

3、这种结构的优缺点

伤害

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

益处

写操作时，只能锁定该元素所在的Segment，而不会影响其他Segment。这样，在最理想的情况下，ConcurrentHashMap最多可以支持同时对多个Segments进行写操作（只是这些写操作均匀分布在所有Segment上）。

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

04 JDK1.8的CurrentHashMap实现原理

JDK8中的ConcurrentHashMap参考了JDK8 HashMap的实现，采用数组+链表+红黑树的实现方式来设计。 CAS操作在内部被广泛使用。这里我简单介绍一下CAS。

CAS是compare and swap的缩写，也就是我们所说的比较和交换。 Cas是基于锁的操作，并且是乐观锁。 Java中的锁分为乐观锁和悲观锁。

悲观锁会锁定资源，直到先前获取锁的线程在下一个线程可以访问该锁之前释放该锁。

乐观锁采取了广泛的态度，以某种方式在不加锁的情况下处理资源，例如为记录添加版本来获取数据。与悲观锁相比，性能有很大提升。

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

节点：保存key、value以及key的哈希值的数据结构。 value 和 next 都用 volatile 修改，以保证并发可见性。

class Node implements Map.Entry {
   final int hash;
   final K key;
   volatile V val;
   volatile Node next;
   //... 省略部分代码} 

Java 8 ConcurrentHashMap结构与Java 8 HashMap基本相同，但保证了线程安全。

在JDK8中ConcurrentHashMap的结构中，由于红黑树的引入，导致ConcurrentHashMap的实现非常复杂。我们都知道红黑树是一种性能非常好的二叉搜索树，其搜索性能为O(logN)，但是实现过程也非常复杂，可读性很差，Doug

莉亚的思维能力确实不是常人能比的。早期完全采用链表结构时，Map的搜索时间复杂度是O(N)。在JDK8中，ConcurrentHashMap当链表长度大于一定阈值时，会将链表转换为红黑树。进一步提高其搜索性能。

05 CurrentHashMap实现原理总结

ConcurrentHashMap的数据结构由JDK1.7版本中的ReentrantLock+Segment+HashEntry变为JDK1.8版本中的synchronized+CAS+HashEntry+红黑树结构存储。

1.数据结构

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

2.保证线程安全机制

JDK1.7使用Segment的分段锁机制来实现线程安全，其中Segment继承自ReentrantLock。 JDK1.8使用CAS+Synchronized来保证线程安全。

3. 锁定粒度

以前是锁定需要数据操作的Segments，现在调整为锁定每个数组元素（Node）。

4. 将链表转换为红黑树

简化定位节点的哈希算法会带来弊端，加剧哈希冲突。因此，当链表节点数大于8时，链表将转换为红黑树进行存储。

5.查询时间复杂度

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

以上就是ConcurrentHashMap的实现原理的详细分析。欢迎在评论区留言交流或拓展。

我是麦克陈|陈锐.我关注【mikechen的互联网架构】，有10年+BAT架构技术来教我。

本文已同步我的技术博客，更新为我原创的《30W+字各大工厂架构技术合集》。