高薪程序员&面试题精讲系列47之说说JDK8中ConcurrentHashMap的底层原理，HashMap与ConcurrentHashMap有什么区别？

高薪程序员&面试题精讲系列47之说说JDK8中ConcurrentHashMap的底层原理，HashMap与ConcurrentHashMap有什么区别？ 一. 面试题及剖析 1. 今日面试题

ConcurrentHashMap的底层原理是什么？

ConcurrentHashMap中涉及到了哪些数据结构?

ConcurrentHashMap为什么是线程安全的？

HashMap与ConcurrentHashMap有什么不同？

JDK 7中的ConcurrentHashMap与JDK 8中的ConcurrentHashMap有什么区别？

2. 题目剖析

壹哥在前面2篇文章中，给大家介绍了ConcurrentHashMap的通用功能、特点，以及JDK 7中ConcurrentHashMap的底层数据机构等内容，文章链接如下：

高薪程序员&面试题精讲系列45之你熟悉ConcurrentHashMap吗？

高薪程序员&面试题精讲系列46之说说JDK7中ConcurrentHashMap的底层原理，有哪些数据结构

但因为ConcurrentHashMap在JDK 7与JDK 8两个不同的版本中，改动较大，所以我们需要分版本来进行分析。本文重点分析JDK 8中的ConcurrentHashMap的底层原理，请各位童鞋拿出笔记做好记录哦！ 

二. JDK 8中ConcurrentHashMap的设计原理【重点】 1. 概述

在JDK 8中，ConcurrentHashMap相对于JDK 7版本做了很大的改动，从实现的代码量上就可以看出来，JDK 7中ConcurrentHashMap不到2000行代码，而JDK 8中则有6000多行代码。

JDK 8中放弃了臃肿的Segment设计，取而代之采用了 Node数组 + 链表 + 红黑树 + CAS + Synchronized 技术来保证并发安全，实现并发控制 *** 作。但在 ConcurrentHashMap的实现中保留了 Segment 的定义，这是为了 保证序列化时的兼容性，但并没有任何结构上的用处。

在JDK 8中用synchronized替换ReentrantLock的原因大致如下:

• 减少内存开销: 如果使用ReentrantLock，就需要节点继承AQS来获得同步支持，这增加了内存开销，而JDK 8中只有头节点需要进行同步。
• 内部优化: synchronized是JVM直接支持的，JVM能够在运行时作出相应的优化措施，比如 锁粗化、锁消除、锁自旋等。

2. synchronized锁

有的人会很好奇，为什么JDK 8中的ConcurrentHashMap会使用synchronized锁，它的性能不是挺低吗？其实我们应该抛弃原有的观念，重新认识synchronized了。

synchronized作为Java中自带的锁机制，之前一直都是一种重量级锁，执行性能较差。但很多东西都不是一成不变的，Java 1.6中其实已经对synchronized进行了优化，优化之后性能已经有了大幅提升。这个优化的点，主要是针对 synchronized 获取锁的方式，对锁的获取方式进行了升级优化。它会先对某一个线程使用偏向锁，如果不行，则再次获取锁；如果又失败，就升级为 CAS 轻量级锁；如果还失败就会短暂自旋，防止线程被系统挂起。最后，如果以上加锁 *** 作都失败了，就升级为重量级锁。synchronized是一步步升级上去的，并不会一开始就利用重量级锁，起初也是通过很多轻量级的方式锁定的。所以，synchronized的升级历程可以总结如下：偏向锁–>CAS轻量级锁–>自旋–>重量级锁。

3. CAS机制

这里 壹哥 给大家简单说一下CAS机制。

CAS是compare and swap的缩写，即我们所说的 比较交换。我们知道Java中的锁分为乐观锁和悲观锁，而CAS是一种乐观锁。悲观锁的思想是将资源直接锁住，等到之前获得锁的线程释放了锁之后，下一个线程才可以访问。而乐观锁采取了一种更宽容的态度，通过某种不加锁的方式来处理资源，比如通过 给记录加version版本号来获取数据，性能较悲观锁有很大的提高。

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

CAS可以在保证性能的同时兼顾并发时的线程安全性，它最典型的应用莫过于 AtomicInteger，因为CAS属于原子 *** 作的一种，能够 保证读写 *** 作是原子的。CAS通过 将内存中的值与期望值进行比较，只有在两者相等时才会对内存中的值进行修改。Java 中 CAS 的实现位于 sun.misc.Unsafe 类中，该类中定义了大量的 native 方法。CAS 的实现有以下几个方法:

public final native boolean compareAndSwapObject(Object o, long offset, Object expected, Object x);

public final native boolean compareAndSwapInt(Object o, long offset, int expected, int x);

public final native boolean compareAndSwapLong(Object o, long offset, long expected, long x);

上面的几个方法，我们只能看到定义，并不能看到具体的实现，具体的实现依赖于 *** 作系统。这里我们只需要简单了解这几个方法里的参数是啥意思就行了:

• o: 目标 *** 作对象；
• offset: 目标 *** 作数的内存偏移地址；
• expected: 期望值；
• x: 更新值。

CAS机制虽然无需加锁、安全且高效，但也存在一些缺点，概括如下:

• 循环检查的时间可能较长，不过可以限制循环检查的次数;
• 只能对一个共享变量执行原子 *** 作;
• 存在 ABA问题(ABA 问题是指在 CAS两次检查 *** 作期间，目标变量的值先由 A 变为 B，又再变回 A，但是 CAS看不到这中间的变换，对它来说目标变量的值并没有发生变化，一直是 A，所以 CAS *** 作会继续更新目标变量的值)。

4. 底层数据结构

在存储结构上，JDK 8中的ConcurrentHashMap放弃了HashEntry，采用了跟 HashMap中一样的Node结构，所以JDK 8的ConcurrentHashMap底层是 Node数组+链表+红黑树(链表长度>=8时转成红黑树)，这就个数据结构就跟HashMap是一样的了。

ConcurrentHashMap在JDK 8中的底层实现，相比于JDK 7来说发生了巨大的变化。取消了 Segment分段锁 + HashEntry数组 + 链表 的数据结构，取而代之的是 Node数组+链表+红黑树 的结构。而对于锁的粒度，则调整为对每个Node数组元素加锁，并且 定位节点的hash算法 也被简化了。这样带来的弊端是 Hash冲突 会加剧，因此在链表节点数量>=8时，会将链表转化为红黑树进行存储。这样一来，查询的时间复杂度就会由原先的 O(n) 变为 O(logN)。如下图所示:

5. ConcurrentHashMap的默认构造方法

在JDK 8中，ConcurrentHashMap有一个默认的无参构造函数，其源码如下:

public ConcurrentHashMap() {
}

我们会发现，这个构造函数啥也没干，那为啥要这样设计呢？这样做的好处是实现了 懒加载(lazy-load )，有效地避免了在初始化时的开销，提高了初始化时的速度，这也是JDK 7中的ConcurrentHashMap被很多人抱怨的地方。

6. ConcurrentHashMap的核心属性

接下来我们再来看看ConcurrentHashMap中的几个核心参数，每个参数的作用含义我已通过注释表明，大家仔细查看即可。

//这个Node数组就是ConcurrentHashMap用来存储数据的哈希表。
transient volatile Node[] table

//这是默认的哈希表数组初始化大小
private static final int DEFAULT_CAPACITY = 16;

//链表转化为红黑树时的阈值
static final int TREEIFY_THRESHOLD = 8

//这个标识位用于识别扩容时是否正在转移数据
static final int MOVED = -1

//计算哈希值时用到的参数，用来去除符号位
static final int HASH_BITS = 0x7fffffff;

//数据转移时，新的哈希表数组
private transient volatile Node[] nextTable;

7. ConcurrentHashMap的核心类

在上面介绍核心参数的章节中，我们可以看到JDK 8的ConcurrentHashMap中，有如下几个核心类:

7.1 Node类

Node是ConcurrentHashMap的核心内部类，它包装了key-value键值对，所有插入到ConcurrentHashMap中的数据都包装在这里面。

Node类源码如下:

static class Node implements Map.Entry {
        final int hash;
        final K key;
        volatile V val;
        volatile Node next;

...        
}

从源码中可以看到，Node类跟HashMap中的Node类是一样的，Key 字段被 final 修饰，说明在生命周期内，key 是不可变的；val 和 next 字段被 volatile 修饰了，这就保证了 val 和 next 字段的可见性。

7.2 TreeNode类

TreeNode是红黑树的节点类，TreeNode不会直接链接到位桶的table[i]位置上，而是由TreeBin链接，TreeBin会作为红黑树的根结点。当链表的长度>=8时，会转换为TreeNode类型的节点。我们要注意，此时的TreeNode并不是红黑树对象，链表并不会直接转换为红黑树，而是由TreeBin对红黑树进行包装。

7.3 TreeBin类

TreeBin是TreeNode节点的包装对象，可以认为是红黑树对象，它代替了TreeNode的根节点，在ConcurrentHashMap的Node“数组”中，存放就是TreeBin对象，而不是TreeNode对象。如下图所示:

这里进行链表转红黑树时，位桶中之所以没有直接用TreeNode作为红黑树的根节点，主要是因为红黑树的 *** 作比较复杂，包括构建、左旋、右旋、删除，平衡等 *** 作。这里用一个代理节点TreeBin来包含这些复杂 *** 作，符合“职责分离”的思想，另外TreeBin中也包含了一些加/解锁 *** 作。

7.4 ForwardingNode类

当进行扩容时，需要把链表旧数组中的数据迁移到新数组中。在做这个 *** 作时，会先把数组中的头节点替换为ForwardingNode对象，ForwardingNode中不保存key和value，只保存了扩容后哈希表(nextTable)的引用，所以该结点仅仅在扩容时才会使用。如果此时要利用get(key)方法查找到相应的Node，会根据key的hash值，映射到一个ForwardingNode节点上，然后再从这个ForwadingNode结点中的nextTable字段里找到新数组的引用，接着再从nextTable中查找具体的键值对。如下图所示:

7.5 ReservationNode类

table数组中除了可以存放Node、TreeBin和ForwadingNode对象之外，还可以存放另一种特殊类型的结点ReservationNode，这是一个保留节点，它的hash值固定为-3， 不保存实际数据，只在computeIfAbsent和compute这两个函数式API中充当占位符加锁使用。

三. HashMap与ConcurrentHashMap的对比(重点)

本节相关面试题:

HashMap与ConcurrentHashMap的区别是什么？

在JDK 8中，HashMap与ConcurrentHashMap的数组、链表结构几乎相同，也都实现了Map接口，继承了AbstractMap抽象类，所以大多数的方法也都是相同的。HashMap中有的方法，ConcurrentHashMap也几乎都有，所以当我们需要从HashMap 切换到ConcurrentHashMap时，无需关心两者之间的兼容性问题。

但两者的 红黑树结构略有不同，HashMap中红黑树中的节点是 TreeNode，TreeNode中不仅有key、value、next、hash等属性，还维护着红黑树的结构，比如说查找，新增等。

而ConcurrentHashMap中的 红黑树则被拆分成了两块，TreeNode仅维护属性和查找功能，另外又新增了一个TreeBin节点来维护红黑树结构，并负责根节点的加锁和解锁，而且还新增了ForwardingNode(转移)节点来保证扩容时的线程安全。

另外HashMap中的key、value都可以为空，但是ConcurrentHashMap中的key、value都不能为空，否则会产生空指针异常。

四. 两种版本的ConcurrentHashMap对比(重点)

• ①. 数据结构: JDK 7中ConcurrentHashMap的数据结构主要是ReentrantLock+Segment+HashEntry数组+链表，而在JDK 8中主要是 synchronized+CAS+Node数组+链表+红黑树，取消了Segment分段锁，数据结构变得更简单了。
• ②. 保证线程安全的机制: JDK 7中采用了Segment分段锁机制来保证线程安全，其中Segment继承自ReentrantLock，而JDK 8中则采用CAS+Synchronized来保证线程安全。
• ③. 锁的粒度: JDK 7中是对需要进行 *** 作的Segment进行加锁，而JDK 8中则是对每个Node数组加锁，锁的粒度更细了。
• ④. 链表转化为红黑树: JDK 8中定位结点的hash算法简化了，这会带来一定的弊端，造成Hash冲突的加剧。因此在链表节点数量>=8时，会将链表转化为红黑树进行存储，这样进行遍历 *** 作时效率是比较快的。
• ⑤. 查询时间复杂度: 时间复杂度变小，从原来遍历链表时的O(N)，变成遍历红黑树时的O(logN)。

五. 结语

本篇文章，壹哥 讲解了JDK 8版本的ConcurrentHashMap的底层原理，各位至少需要掌握以上内容，请认真背下来吧。接下来 壹哥 会再通过另一篇文章，给大家讲解 JDK 8中的ConcurrentHashMap的底层源码，请做好准备哦。