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

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

HashMap结构

HashMap 是我们经常会用到的集合类，JDK 1.7 之前底层使用了数组加链表的组合结构，如下图所示：

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