背景
由于HashMap不是线程安全的，因此在并发环境下可能会发生死锁问题，且导致CPU占用率接近100%。
原因是在Java语言在并发情况下使用HashMap造成Race Condition，从而导致死循环。
可以搜索“HashMap Infinite Loop”以深入了解这个问题。
分析
put()方法的执行过程
该问题的成因涉及到四个方法，最初的起因是调用put()方法。
下面，我们来看一下Java的HashMap的源代码。
调用put() 方法一讲一个<Key,Value>添加到HashMap表中：
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);
}
新建一个更大尺寸的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);
}
将数据从老的Hash表中迁移到新的Hash表的过程：
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);
}
}
}
正常的ReHash的过程
- 我假设了我们的hash算法就是简单的用key mod 一下表的大小（也就是数组的长度）。
- 最上面的是old hash 表，其中的Hash表的size=2, 所以key = 3, 7, 5，在mod 2以后都冲突在table[1]这里了。
- 接下来的三个步骤是Hash表 resize成4，然后所有的<key,value> 重新rehash的过程
并发下的Rehash
假设我们有两个线程，在下图中分别用红色和浅蓝色标注。
同时，假设线程一执行到下面代码位置就被调度器挂起了，而轮到线程二执行。
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);
线程一被挂起时，处于以下状态：
而线程二开始执行了，执行完了整个rehash过程，此时状态如下图所示：
值得一提的是，这时，key为7的next指针指向了key为3的元素。
这时，又轮到线程一执行了（线程一被调度回来），紧接着执行循环体中的下面三句代码：
e.next = newTable[i];
newTable[i] = e;
e = next;
此时的状态如下所示：
这时候一切正常。
线程一继续执行下一个循环：
当执行完 Entry<K,V> next = e.next; 后：
继续执行下面代码：
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
执行完成后，为此状态：
线程一继续仍然再执行下一个循环：
Entry<K,V> next = e.next;
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
执行完成 Entry<K,V> next = e.next; 后，如下情况：
接下来，执行 e.next = newTable[i]; 后会导致下面的情况：
而执行完 newTable[i] = e; 和 e = next; 后，则会形成环，如下所示：
此后，由于e为null，因此跳出循环。
当调用到hashMap.get()方法，且进入索引为3的Bucket，而且所提供的key不在索引为3的Bucket中所包含的所有元素的key范围内时（比如调用hashMap.get(11)），则会进入无限循环（infinite loop）。
Reference
- 疫苗：JAVA HASHMAP的死循环 - https://coolshell.cn/articles/9606.htmlw