HashMap死循环问题

一、HashMap简介：

1、数据结构

image.png

数组+链表的结构，每一对k:v都封装成一个entry，通过链表解决冲突和碰撞。

put(k, v)：首先对key哈希找到table对应的位置index，如果该位置没有entry，直接放进去，如果该位置已经有entry了，插入表头；

当table里的元素达到一定阈值的时候，通过rehash扩大table的大小(2倍)降低冲突/碰撞率；

2、HashMap存在的问题：

• 线程不安全

• 丢失数据：put进去一个元素，get却是null

• 死循环，CPU利用率被打满

二、一个完美的HashMap死循环是如何产生的

如何产生的：多线程，put操作导致rehash，把元素从旧table拷贝(transfer)到新table中时，可能产生死循环。

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

1、正常的ReHash过程

我假设了我们的hash算法就是简单的用key mod 一下表的大小（也就是数组的长度）。

最上面的是old hash 表，其中的Hash表的size=2, 所以key = 3, 7, 5，在mod 2以后都冲突在table1这里了。

接下来的三个步骤是Hash表 resize成4，然后所有的 重新rehash的过程。

image.png

2、并发的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);

假设线程1在上述代码注释处被挂起了，而我们的线程二执行完成了，于是我们有下面的这个样子：

image.png

此时线程1回来继续执行：

image.png
线程一接着工作，把key(7)摘下来，放到newTable[i]的第一个，然后把e和next往下移：
image.png

环形链出现：

image.png
此时如果我们执行map.get(11)就会陷入死循环，慢慢耗尽CPU。

三、解决方案

1. 用HashTable替换HashMap
2. 加锁，线程同步
3. 用concurrentHashMap替换HashMap

参考：https://www.cnblogs.com/andy-zhou/p/5402984.html