ConcurrentHashMap的实现原理

Bertha 。 2022-05-15 08:04 187阅读 0赞

HashMap是Java当中很常用的数据结构。

但是HashMap不是线程安全的，单线程环境下还可以正常使用，不过在并发插入元素的时候有可能出现带环链表，让下一次读操作出现死循环。

那么什么样的哈希数据结构可以保证线程安全呢？

线程安全的哈希数据结构主要有HashTable和ConcurrentHashMap。而ConcurrentHashMap比HashTable的扩展性更好。

在多并发场景下，我们通常采用ConcurrentHashMap，这个集合类兼顾了线程安全和性能。

那么在并发场景下，ConcurrentHashMap是怎么保证线程安全的，又是怎么实现高性能读写的呢？

在细说ConcurrentHashMap之前，先来回顾一下HashMap。

我们来简单回顾一下HashMap的结构：

![70][]

简单来说，HashMap是一个Entry对象的数组。数组中的每一个Entry元素，又是一个链表的头节点。

Hashmap不是线程安全的。在高并发环境下做插入操作，有可能出现下面的环形链表：

![70 1][]

想要避免HashMap的线程安全问题有很多种方法，比如改用HashTable或者Collections.SynchronizedMap。但是，这两者有着共同的问题：性能。无论读操作还是写操作，他们都会给整个集合加锁，导致同一时间的其他操作为之阻塞。

![70 2][]

![70 3][]

在并发环境下，如何能够兼顾线程安全和运行效率呢？这时候ConcurrentHashMap就应运而生了。

那么，比起HashMap，ConcurrentHashMap有什么特别之处呢？

掌握HashMap之后，学习ConcurrentHashMap其实很简单，最关键是要理解一个概念：\[Segment\]。

Segment是什么呢？Segment本身就相当于一个HashMap对象。

同HashMap一样，Segment包含一个HashEntry数组，数组中的每一个HashEntry既是一个键值对，也是一个链表的头节点。

单一的Segment结构如下：

![70 4][]

像这样的Segment对象，在ConcurrentHashMap集合中有多少个呢？有2的N次方个，共同保存在一个名为segments的数组当中。

因此整个ConcurrentHashMap的结构如下：

![70 5][]

可以说，ConcurrentHashMap是一个二级哈希表。在一个总的哈希表下面，有若干个子哈希表。

这样的二级结构，和数据库的水平拆分有些相似。

那么ConcurrentHashMap这样的设计有什么好处呢？

ConcurrentHashMap优势就是采用了\[锁分段技术\]，每个Segment就好比一个自治区，读写操作高度自治，Segment之间互不影响。

下面我们来看看ConcurrentHashMap并发读写的几种情形：

**Case1：不同Segment的并发写入**

**![70 6][]**

不同Segment的写入是可以并发执行的。

**Case2：同一Segment的一写一读**

**![70 7][]**

同一Segment的写和读是可以并发执行的。

**Case3：同一Segment的并发写入**

**![70 8][]**

同一Segment的并发写入是需要上锁的，因此对同一Segment的并发写入获取不到锁的线程会被阻塞。

不同Segment之间和同一Segment之内的读读操作都是不互斥的，因为读不涉及到对数据的修改操作。

由此可见，ConcurrentHashMap当中每个Segment各自持有一把锁。在保证线程安全的同时降低了锁的粒度，让并发操作效率更高。

ConcurrentHashMap的Segment之间的读写操作大致就是这样。那么ConcurrentHashMap的读写过程具体是什么样子呢？

我们来看一下ConcurrentHashMap读写的详细过程：

**Get方法：**

1.为输入的Key做Hash运算，得到hash值。

2.通过hash值，定位到对应的Segment对象。

3.再次通过hash值，定位到Segment当中数组的具体位置。

**Put方法：**

1.为输入的Key做Hash运算，得到hash值。

2.通过hash值，定位到对应的Segment对象。

3.获取可重入锁。

4.再次通过hash值，定位到Segment当中数组的具体位置。

5.插入或覆盖HashEntry对象。

6.释放锁。

从步骤可以看出，ConcurrentHashMap在读写时都需要二次定位。首先定位到Segment，之后定位到Segment内的具体数组下标。

既然每个Segment都各自加锁，那么在调用size( )方法的时候，怎么解决一致性的问题呢？

Size方法的目的是统计ConcurrentHashMap的总元素数量， 自然需要把各个Segment内部的元素数量汇总起来。

但是，如果在统计Segment元素数量的过程中，已统计过的Segment瞬间插入新的元素，这时候该怎么办呢？

![70 9][]

![70 10][]

![70 11][]

关于这一点，我们来看看ConcurrentHashMap的size( )操作是怎样工作的：

ConcurrentHashMap的Size方法是一个嵌套循环，大体逻辑如下：

1.遍历所有的Segment。

2.把Segment的元素数量累加起来。

3.把Segment的修改次数累加起来。

4.判断所有Segment的总修改次数是否大于上一次的总修改次数。如果大于，说明统计过程中有修改，重新统计，尝试次数+1；如果不是。说明没有修改，统计结束。

5.如果尝试次数超过阈值，则对每一个Segment加锁，再重新统计。

6.再次判断所有Segment的总修改次数是否大于上一次的总修改次数。由于已经全部加锁，统计过程中肯定没有修改，统计的一定是正确的结果。

7.释放锁，统计结束。

官方源代码如下：

public int size() {
        // Try a few times to get accurate count. On failure due to
       // continuous async changes in table, resort to locking.
       final Segment<K,V>[] segments = this.segments;
        int size;
        boolean overflow; // true if size overflows 32 bits
        long sum;         // sum of modCounts
        long last = 0L;   // previous sum
        int retries = -1; // first iteration isn't retry
        try {
            for (;;) {
                if (retries++ == RETRIES_BEFORE_LOCK) {
                    for (int j = 0; j < segments.length; ++j)
                        ensureSegment(j).lock(); // force creation
                }
                sum = 0L;
                size = 0;
                overflow = false;
                for (int j = 0; j < segments.length; ++j) {
                    Segment<K,V> seg = segmentAt(segments, j);
                    if (seg != null) {
                        sum += seg.modCount;
                        int c = seg.count;
                        if (c < 0 || (size += c) < 0)
                            overflow = true;
                    }
                }
                if (sum == last)
                    break;
                last = sum;
            }
        } finally {
            if (retries > RETRIES_BEFORE_LOCK) {
                for (int j = 0; j < segments.length; ++j)
                    segmentAt(segments, j).unlock();
            }
        }
        return overflow ? Integer.MAX_VALUE : size;
    }

为什么这样设计呢？这种思想和乐观锁悲观锁的思想如出一辙。

为了尽量不锁住所有Segment，首先乐观地假设Size过程中不会有修改。当尝试一定次数，才无奈转为悲观锁，锁住所有Segment保证强一致性。

**几点说明：**

1. 这里介绍的ConcurrentHashMap原理和代码，都是基于Java1.7的。在Java8中会有些许差别。

2.ConcurrentHashMap在对Key求Hash值的时候，为了实现Segment均匀分布，进行了两次Hash。有兴趣的同学可以研究一下源代码。

关于ConcurrentHashMap的实现原理就介绍到这里了。

参考：[程序员小灰--《什么是ConcurrentHashMap？》][--_ConcurrentHashMap]

[70]: /images/20220515/36a2b2ff2d484c98ad4ab31837c5c80f.png
[70 1]: /images/20220515/afec1d5565be4bb09e9f23bffb2de57f.png
[70 2]: /images/20220515/f75162eb7abc4d9eb8e58d5f10c60b69.png
[70 3]: /images/20220515/f685f1d4ec514ff7bd5a9c907f38ed91.png
[70 4]: /images/20220515/5ccb187d7d364be299158c51cfc8b8c0.png
[70 5]: /images/20220515/460dc28d351345ce8ba7f219fbacae02.png
[70 6]: /images/20220515/2e2a35ce20314920994e955939ab4d88.png
[70 7]: /images/20220515/5c2cea611a814934a9925ba479cf910d.png
[70 8]: /images/20220515/e3f0fe7b5c47491c81f257ba4e9b7bf9.png
[70 9]: /images/20220515/615faf151dc74ee4ba0bd63bda63af33.png
[70 10]: /images/20220515/9299e3ca07d94b4cb783354077105d6a.png
[70 11]: /images/20220515/3c2d4594ec2e4e1bb0ff860dfe5e0560.png
[--_ConcurrentHashMap]: https://mp.weixin.qq.com/s/1yWSfdz0j-PprGkDgOomhQ