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

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

ConcurrentHashMap的底层原理是什么？

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

ConcurrentHashMap为什么是线程安全的？

为什么ConcurrentHashMap的读 *** 作不需要加锁？

2. 题目剖析

壹哥在上一篇文章中，开始给大家介绍ConcurrentHashMap，重点介绍了ConcurrentHashMap的通用功能、特点等内容，文章链接如下：

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

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

二. JDK 7中ConcurrentHashMap的设计原理【重点】

本节相关面试题:

ConcurrentHashMap的底层原理是什么？

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

虽然JDK 7及其之前版本的API，我们现在开发时已经很少用了，但有些面试官就喜欢问一些古董问题，并且也有些古董级的项目在使用这种陈旧的API，所以基于这种现实，壹哥 还是带大家来了解一下JDK 7中的ConcurrentHashMap。

1. 概述

在JDK 7版本中，ConcurrentHashMap和HashMap的设计思路其实是差不多的，但为了支持并发 *** 作，做了一定的改进。比如ConcurrentHashMap中的数据是一段一段存放的，我们把这些分段称之为Segment分段，在每个Segment分段中又有 数组+链表 的数据结构。默认情况下ConcurrentHashMap把主干分成了 16个Segment分段，并对每一段都单独加锁，我们把这种设计策略称之为 "分段锁"， ConcurrentHashMap就是利用这种分段锁机制进行并发控制的。JDK 7中ConcurrentHashMap的基本数据结构如下图所示：

在理想状态下，ConcurrentHashMap可以 同时支持16个线程 执行并发写 *** 作，以及任意数量的线程进行并发读 *** 作。在写 *** 作时，通过分段锁技术，只对所 *** 作的段加锁而不会影响其它分段，且在读 *** 作时(几乎)不需要加锁。

2. Segment分段

上文给大家提到了Segment分段的概念，接下来 壹哥 再对其做个详细的介绍。

Segment翻译过来是 片段、部分 的意思，我们一般称之为 段 或者 槽。默认情况下一个ConcurrentHashMap中有16个Segment分段，每个分段都可以独立加锁，我们可以认为这个ConcurrentHashMap的ConcurrentLevel并发等级是16，那么理论上就允许16个线程并发执行。在多线程并发环境下，对不同Segment分段里的数据进行 *** 作是不用考虑锁竞争的。所以，对同一个Segment的 *** 作才需要考虑线程同步，不同的Segment则无需考虑。

另外Segment分段的数量一旦被初始化分配完毕，就不可再被扩容。而在每个Segment分段里面都维护了一个HashEntry数组，这个数组是可以被扩容的，所以每个Segment分段其实都类似于是一个HashMap。另外Segment类继承自ReentrantLock类，这是一种可重入锁(ReentrantLock)。其源码如下:

static final class Segment extends ReentrantLock implements Serializable {
    transient volatile int count;
    transient int modCount;
    transient int threshold;
    transient volatile HashEntry[] table;
    final float loadFactor;
}

在Segment类中，有5个重要的成员变量，其具体含义如下：

• count：代表Segment中存储的数据元素数量；
• modCount：记录会对table数组中元素数量造成影响的 *** 作次数，比如记录put()、remove()等方法的执行次数；
• threshold：阈值，如果Segment中元素的数量超过该值就会对table数组进行扩容；
• table：HashEntry数组，数组中的每一个元素都是链表中的一个节点；
• loadFactor：负载因子，用于确定threshold阈值进行扩容，与HashMap中的负载因子作用一样。

经过 壹哥 这么一描述，你会发现，其实ConcurrentHashMap就类似于是一个“大仓库”。为了高效的利用这个“大仓库”，默认情况下我们可以把这个“大仓库”分成16个“区域”，而每个“区域”内部又可以再划分成若干个“小房间”。我们可以对每个“区域”加锁，这并不会影响其他“区域”货物的“进出”。

3. 分段锁的优劣

从上面的源码中，我们知道Segment继承了一个可重入锁ReentrantLock，由此获取了锁的能力。每个Segment分段锁控制的都是一小段，但当每个Segment越来越大时，锁的粒度也就变大了。

分段锁的优势在于可以确保 *** 作不同Segment分段时的并发执行，而 *** 作同一个Segment分段时需要进行锁的竞争和等待，这相对于对整个HashMap进行synchronized同步锁 *** 作是有优势的。

但分段锁的缺点在于会把一个Map分成很多段(默认是16段)，容易造成内存空间浪费(容易不连续、碎片化)。另外 *** 作Map时，如果竞争同一个分段锁的概率较小，分段锁反而会造成更新等 *** 作的长时间等待；而当某个段很大时，分段锁的性能又会下降。

4. segments[]数组

上面说了，在默认情况下，一个ConcurrentHashMap会被拆分成固定的16个Segment分段，这16个Segment分段就组成了一个segments[]数组，其源码如下:

public class ConcurrentHashMap extends AbstractMap
implements ConcurrentMap, Serializable {

    final Segment[] segments;
    
    ...
}

5. ConcurrentHashMap构造方法核心参数

我们要想使用ConcurrentHashMap，肯定要先构造出其对象。ConcurrentHashMap为我们提供了5个构造方法，其中最重要的一个是带有3个参数的构造方法，源码如下：

public ConcurrentHashMap(int initialCapacity,float loadFactor, int concurrencyLevel) {
    ......
}

该构造方法中的3个核心参数含义如下：

• initialCapacity: 初始总容量，默认16；
• loadFactor: 负载因子，默认0.75；
• concurrencyLevel: 并发级别，默认16，代表集合内部Segment的数量，concurrencyLevel一经指定，不可改变。

这里我们一定要注意，concurrencyLevel并发级别 是用来控制Segment数量的。在ConcurrentHashMap创建后，Segment的数量是不会再变的，即Segment本身无法再扩容，扩容改变的是每个Segment中table数组的大小。这样做的好处是扩容过程不需要对整个ConcurrentHashMap做rehash，只需要对Segment里面的元素做一次rehash就可以了。

对ConcurrentHashMap进行初始化还是很简单的，先是根据concurrencyLevel数量来new出一个Segment数组。这里Segment的数量必须是2的整数倍，且<=concurrencyLevel中最大的那个，这样的好处是方便通过移位操作来进行hash，加快hash的过程。另外intialCapacity用于指定Segment内部的容量大小，也必须是2的整数倍，这同样是为了加快hash的过程。

6. HashEntry简介

在每个Segment分段中，都持有一个HashEntry[] table数组，这个数组类似于HashMap中的Node[] table数组，所以HashEntry与Node类相似，也是K-V结构，并且带有一个next节点。其源码如下:

static final class Segment extends ReentrantLock implements Serializable {
    transient volatile HashEntry[] table;
}

static final class HashEntry {
    final int hash;
    final K key;
    volatile V value;
    volatile HashEntry next;
}

我们从源码中可以看出，HashEntry[] table数组中存储的是一个一个的HashEntry对象，该对象是key-value结构的存储单元。在HashEntry中，除了value属性以外，其他的几个属性都是final修饰的，这样做是为了防止链表结构被破坏，出现ConcurrentModificationException的情况。另外HashEntry可以通过next属性来关联下一个HashEntry对象，其结构如下图所示:

从上图可以看出，ConcurrentHashMap由一个 segments[]数组 组成，该数组的每一个元素都是一个 Segment分段。而在每个Segment分段中，又是一个由 HashEntry数组+链表 组成的结构。由此可见，Segment类似于一个小型的HashMap，我们可以把ConcurrentHashMap理解为HashMap的集合。

7. ConcurrentHashMap的并发 *** 作

本节相关面试题:

ConcurrentHashMap为什么是线程安全的？

在上面的小节中，壹哥 跟大家说过，ConcurrentHashMap的扩容，指的是Segment分段中 HashEntry table[]数组 的扩容，并不是指segments[]数组的扩容。如下图所示:

我们在 *** 作ConcurrentHashMap时，一般就是在 *** 作某一个具体的Segment，而在多线程环境下，不同的线程会 *** 作不同的Segment。所以当我们对ConcurrentHashMap进行并发 *** 作时，只要锁住一个 Segment，其余的Segment依然可以 *** 作。这样只要保证每个 Segment 是线程安全的，就实现了全局的线程安全，彼此互不影响，以此实现了并发 *** 作。

但是当多个线程想要 *** 作同一个分段时，是需要先获取锁的，所有的put()、get()、remove()等方法都会先根据key的 hash值 找到相应的分段，然后再尝试获取锁进行访问。

比如当ConcurrentHashMap进行put() *** 作时，会先根据key找到某个承载数据的具体的Segment分段，然后再竞争获取到Segment的独占锁。获取锁的逻辑很简单，就是进行tryLock()，如果获取锁失败了，就再去执行scanAndLockForPut()方法。scanAndLockForPut()方法的实现逻辑也是比较简单的，就是通过 循环调用tryLock() 进行多次获取。如果循环的次数retries大于事先设置好的MAX_SCAN_RETRIES，就执行lock()方法，此方法会进行阻塞等待，直到成功地拿到Segment锁为止。

8. ConcurrentHashMap的类关系

以上就是JDK 7中的ConcurrentHashMap，最后 壹哥 再给大家简单总结一下。JDK 7 中的ConcurrentHashMap采用了 Segment分段锁(ReentrantLock) + HashEntry数组 +链表 的技术，整个Map被分成了多个段，每个分段中都有自己的Segment分段锁，段与段之间可以实现多线程环境下的并发访问。我们可以用下图来归纳一下，JDK 7中ConcurrentHashMap的类关系:

三. 结语

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