ConcurrentHashMap图文源码解析

冷不防 2021-11-27 01:28 305阅读 0赞

HashMap结构：

![1462784-20190722165240784-1149268176.png][]

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

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

![1462784-20190722165324113-335430609.png][]

避免HashMap线程安全问题的方法：

1.  改用HashTable
2.  Collections.synchronizedMap

但是两者有共同的问题：性能

无论是读操作还是写操作，它们都会给整个集合加锁，导致同一时间其他的操作为之阻塞

![1462784-20190722165633331-437285758.png][]

![1462784-20190722165652422-1251078900.png][]

在并发环境中，如何兼顾线程安全和运行效率呢？

ConcurrentHashmap就应运而生了

ConcurrentHashmap有一个重要的概念：【Segment】

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

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

Segment继承了ReentrantLock，表明每个segment都可以当做一个锁。这样对每个segment中的数据需要同步操作的话都是使用每个segment容器对象自身的锁来实现。只有对全局需要改变时锁定的是所有的segment。

单一的Segment结构如下：

![1462784-20190722165921383-1091068934.png][]

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

因此整个ConcurrentHashMap的结构如下：

![1462784-20190722182823387-132040816.png][]

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

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

ConcurrentHashMap这样设计的好处？

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

ConcurrentHashMap并发读写的情形：

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

![1462784-20190722183045182-127168276.png][]

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

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

**![1462784-20190722183115752-1188417679.png][]**

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

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

![1462784-20190722183140684-94786861.png][]

Segment的写入是需要上锁的，因此对同一Segment的并发写入会被阻塞。

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

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瞬间插入新的元素，这时候该怎么办呢？

![1462784-20190722183805112-211576098.png][]

![1462784-20190722183824959-660879875.png][]

![1462784-20190722183837494-992270633.png][]

![1462784-20190722183851165-242337838.png][]

看一下ConcurrentHashmap是怎么样操作的：

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

1.   遍历所有的Segment
2.  把Segment的元素数量累加起来
3.  把Segment的修改次数累加起来
4.  判断所有Segment的总修改次数是否大于上一次的总修改次数。如果大于，说明统计过程中有修改，重新统计，尝试次数+1；如果不是。说明没有修改，统计结束
5.  如果尝试次数超过阈值，则对每一个Segment加锁，再重新统计
6.  再次判断所有Segment的总修改次数是否大于上一次的总修改次数。由于已经加锁，次数一定和上次相等
7.  释放锁，统计结束

官方源代码如下：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

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中会有些许差别。其中抛弃了原有的 Segment 分段锁，而采用了 CAS + synchronized 来保证并发安全性。
2.  ConcurrentHashMap在对Key求Hash值的时候，为了实现Segment均匀分布，进行了两次Hash。有兴趣的朋友可以研究一下源代码。

本文转发整合：

*  [漫画：什么是ConcurrentHashMap？][ConcurrentHashMap]

转载于:https://www.cnblogs.com/echola/p/11227689.html

[1462784-20190722165240784-1149268176.png]: /images/20211126/74128a6484e44e66b2ac83dc7e0cf844.png
[1462784-20190722165324113-335430609.png]: /images/20211126/82e3bd42fea647c993456748c424d345.png
[1462784-20190722165633331-437285758.png]: /images/20211126/bbc287fc221e409da1072a5f208c690e.png
[1462784-20190722165652422-1251078900.png]: /images/20211126/c4ebeb6e5bba4f2b98db4bad910fe233.png
[1462784-20190722165921383-1091068934.png]: /images/20211126/ad769de45fee44879d820af332973a28.png
[1462784-20190722182823387-132040816.png]: /images/20211126/31a21a94e40941c2bb0f800cdee2ff2f.png
[1462784-20190722183045182-127168276.png]: /images/20211126/a5e0006303f1471692ee73455364ff35.png
[1462784-20190722183115752-1188417679.png]: /images/20211126/f61625e3814e49a5a536493c68cb1833.png
[1462784-20190722183140684-94786861.png]: /images/20211126/5b95e91761ce4ece8db137397febc410.png
[1462784-20190722183805112-211576098.png]: /images/20211126/c340cc45d5bd440da0c251f2ec3e2fd8.png
[1462784-20190722183824959-660879875.png]: /images/20211126/8368235e0b054ef59ab88c65b2be9ccb.png
[1462784-20190722183837494-992270633.png]: /images/20211126/6f970ed619aa4131ac0a2d48597c17cd.png
[1462784-20190722183851165-242337838.png]: /images/20211126/fa3e84eeae4c41e49d59462780973003.png
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211126/0b4a224a68e7483681c106f11e4909dc.png
[ConcurrentHashMap]: https://mp.weixin.qq.com/s/1yWSfdz0j-PprGkDgOomhQ