HashMap引发死链问题（HashMap、ConcurrentHashMap原理解析）

墨蓝 2023-07-20 08:26 8阅读 0赞

## 事故背景 ##

一个CPU使用率飙升至100%的线上故障，原因是在并发情况下使用HashMap导致死循环。  
当cpu使用率100%时，查看堆栈，发现程序都卡在了`HashMap.get()`这个方法上了，重启程序后问题消失。但是过段时间又会来。

## HashMap结构 ##

`HashMap` 是我们经常会用到的集合类，`JDK 1.7` 之前底层使用了数组加链表的组合结构，如下图所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzNDA0Mzk1_size_16_color_FFFFFF_t_70]

`HashMap`通常会用一个指针数组（假设为`table[]`）来做分散所有的`key`，当一个`key`被加入时，会通过Hash算法通过`key`算出这个数组的下标`i`，然后就把这个`<key, value>`插到`table[i]`中，如果有两个不同的`key`被算在了同一个`i`，那么就叫`冲突`，又叫`碰撞`，这样会在`table[i]`上形成一个链表。

如果`table[]`的尺寸很小，比如只有2个，如果要放进10个keys的话，那么碰撞非常频繁，于是一个`O(1)`的查找算法，就变成了链表遍历，性能变成了`O(n)`，这是Hash表的缺陷。

所以，Hash表的尺寸和容量非常的重要。一般来说，Hash表这个容器当有数据要插入时，都会检查容量有没有超过设定的`thredhold`，如果超过，需要增大Hash表的尺寸，但是这样一来，整个Hash表里的无素都需要被重算一遍。这叫`rehash`，这个成本相当的大。

--------------------

## JDK 1.7 HashMap的`rehash`源代码 ##

Put一个`Key,Value`对到Hash表中：

public V put(K key, V value)
    { 
        ......
        //算Hash值
        int hash = hash(key.hashCode());
        int i = indexFor(hash, table.length);
        //如果该key已被插入，则替换掉旧的value （链接操作）
        for (Entry<K,V> e = table[i]; e != null; e = e.next) { 
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { 
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        modCount++;
        //该key不存在，需要增加一个结点
        addEntry(hash, key, value, i);
        return null;
    }

检查容量是否超标

void addEntry(int hash, K key, V value, int bucketIndex)
    { 
        Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
        //查看当前的size是否超过了我们设定的阈值threshold，如果超过，需要resize
        if (size++ >= threshold)
            resize(2 * table.length);
    }

新建一个更大尺寸（2倍）的hash表，然后把数据从老的Hash表中迁移到新的Hash表中。

void resize(int newCapacity)
    { 
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        ......
        //创建一个新的Hash Table
        Entry[] newTable = new Entry[newCapacity];
        //将Old Hash Table上的数据迁移到New Hash Table上
        transfer(newTable);
        table = newTable;
        threshold = (int)(newCapacity * loadFactor);
    }

迁移的源代码：

void transfer(Entry[] newTable)
    { 
        Entry[] src = table;
        int newCapacity = newTable.length;
        //下面这段代码的意思是：
        // 从OldTable里摘一个元素出来，然后放到NewTable中
        for (int j = 0; j < src.length; j++) { 
            Entry<K,V> e = src[j];
            if (e != null) { 
                src[j] = null;
                do { 
                    Entry<K,V> next = e.next;
                    int i = indexFor(e.hash, newCapacity);
                    e.next = newTable[i];
                    newTable[i] = e;
                    e = next;
                } while (e != null);
            }
        }
    }

--------------------

旧数组元素迁移到新数组时，依旧采用`头插入法`，这样将会导致新链表元素的逆序排序。

多线程并发`扩容`的情况下，链表可能形成死链（环形链表）。一旦有任何查找元素的动作，线程将会陷入死循环,从而引发 CPU 使用率飙升。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzNDA0Mzk1_size_16_color_FFFFFF_t_70 1]

--------------------

## JDK1.8 改进方案 ##

JDK1.8 `HashMap` 底层结构进行彻底重构，使用`数组`加`链表/红黑树`方式这种组合结构。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzNDA0Mzk1_size_16_color_FFFFFF_t_70 2]  
新元素依旧通过取模方式获取 `Table` 数组位置，然后再将元素加入链表尾部。一旦链表元素数量超过 `8` 之后，自动转为`红黑树`，进一步提高了查找效率。

由于 JDK1.8 链表采用`尾插入法`，从而避免`并发扩容`情况下链表形成死链的可能。

但是HashMap在JDK1.8仍然不适合用于并发场景，依然是无法避免并发扩容情况下的`死链`问题。（`并发赋值时被覆盖`、`size 计算问题`）

--------------------

## ConcurrentHashMap ##

#### JDK1.7 ConcurrentHashMap结构 ####

JDK1.7 ConcurrentHashMap 数据结构如下所示:

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzNDA0Mzk1_size_16_color_FFFFFF_t_70 3]

`Segament` 是一个`ConcurrentHashMap`内部类，底层结构与 `HashMap` 一致。另外`Segament` 继承自 `ReentrantLock`。

当新元素加入 `ConcurrentHashMap` 时，首先根据 key `hash` 值找到相应的 `Segament`。接着直接对 `Segament` 上锁，若获取成功，后续操作步骤如同 `HashMap`。

由于锁的存在，`Segament` 内部操作都是并发安全，同时由于其他 `Segament` 未被占用，因此可以支持 `concurrencyLevel` 个线程安全的并发读写。

#### size 统计问题 ####

虽然 `ConcurrentHashMap` 引入分段锁解决多线程并发的问题，但是同时引入新的复杂度，导致计算 `ConcurrentHashMap` 元素数量将会变得复杂。

由于 `ConcurrentHashMap` 元素实际分布在 `Segament` 中，为了统计实际数量，只能遍历 `Segament`数组求和。

为了数据的准确性，这个过程过我们需要锁住所有的 `Segament`，计算结束之后，再依次解锁。不过这样做，将会导致写操作被阻塞，一定程度降低 `ConcurrentHashMap`性能。  
所以这里对 `ConcurrentHashMap`\#size 统计方法进行一定的优化。

`Segment` 每次被修改（写入，删除）,都会对 modCount（更新次数）加 1。只要相邻两次计算获取所有的 `Segment` modCount 总和一致，则代表两次计算过程并无写入或删除，可以直接返回统计数量。  
如果三次计算结果都不一致，那没办法只能对所有 Segment 加锁，重新计算结果。  
这里需要注意的是，这里求得 size 数量不能做到 100% 准确。这是因为最后依次对 Segment 解锁后，可能会有其他线程进入写入操作。这样就导致返回时的数量与实际数不一致。  
不过这也能被接受，总不能因为为了统计元素停止所有元素的写入操作。

#### 性能问题 ####

想象一种极端情况的，所有写入都落在同一个 `Segment`中，这就导致`ConcurrentHashMap` 退化成 `SynchronizedMap`，共同抢一把锁。

#### JDK1.8 改进方案 ####

JDK1.8 之后，`ConcurrentHashMap` 取消了分段锁的设计，进一步减锁冲突的发生。另外也引入红黑树的结构，进一步提高查找效率。

数据结构如下所示：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzNDA0Mzk1_size_16_color_FFFFFF_t_70 4]  
`Table` 数组的中每一个 `Node` 我们都可以看做一把锁，这就避免了 `Segament` 退化问题。

另外一旦 `ConcurrentHashMap` 扩容， Table 数组元素变多，锁的数量也会变多，并发度也会提高。

JDK1.8 使用 CAS 方法加 `synchronized` 方式，保证并发安全。

--------------------

## 总结 ##

*  `HashMap` 在多线程并发的过程中存在死链与丢失数据的可能，不适合用于多线程并发使用的场景的,我们可以在方法的局部变量中使用。
 *  `SynchronizedMap` 虽然线程安全，但是由于锁粒度太大，导致性能太低，所以也不太适合在多线程使用。
 *  `ConcurrentHashMap` 由于使用多把锁，充分降低多线程并发竞争的概率，提高了并发度，非常适合在多线程中使用。`ConcurrentHashMap` 分段锁的经典思想，我们可以应用在热点更新的场景，提高更新效率。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzNDA0Mzk1_size_16_color_FFFFFF_t_70]: /images/20230528/3cc832d0546a463aac3b4169843b4008.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzNDA0Mzk1_size_16_color_FFFFFF_t_70 1]: /images/20230528/303c838b27e24dfeb280e4506ed62479.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzNDA0Mzk1_size_16_color_FFFFFF_t_70 2]: /images/20230528/d6deb3a69be041509d09947e97030c7b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzNDA0Mzk1_size_16_color_FFFFFF_t_70 3]: /images/20230528/597ec589f76d47d2a2083020be12edb0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzNDA0Mzk1_size_16_color_FFFFFF_t_70 4]: /images/20230528/1fd5f6f2c477488dbc5229346748206c.png