【Java面试】HashMap死循环问题

问题

最近几道面试题被问了是否了解并发情况下JDK7中HashMap发生死循环，导致CPU占用100%的问题。
由于HashMap并非是线程安全的，所以在高并发的情况下必然会出现问题，这是一个普遍的问题。

如果是在单线程下使用HashMap，自然是没有问题的，如果后期由于代码优化，这段逻辑引入了多线程并发执行，在一个未知的时间点，会发现CPU占用100%，居高不下，通过查看堆栈，你会惊讶的发现，线程都Hang在hashMap的get()方法上，服务重启之后，问题消失，过段时间可能又复现了。
这是为什么？

原因分析

在了解来龙去脉之前，我们先看看JDK7中HashMap的数据结构。
在内部，HashMap使用一个Entry数组保存key、value数据（JDK8之后是Node），当一对key、value被加入时，会通过一个hash算法得到数组的下标index，算法很简单，根据key的hash值，对数组的大小取模 hash & (length-1)，并把结果插入数组该位置，如果该位置上已经有元素了，就说明存在hash冲突，这样会在index位置生成链表。
如果存在hash冲突，最惨的情况，就是所有元素都定位到同一个位置，形成一个长长的链表，这样get一个值时，最坏情况需要遍历所有节点，性能变成了O(n)，所以元素的hash值算法和HashMap的初始化大小很重要。
当插入一个新的节点时，如果不存在相同的key，则会判断当前内部元素是否已经达到阈值（默认是数组大小的0.75），如果已经达到阈值，会对数组进行扩容，也会对链表中的元素进行rehash。

JDK7中HashMap代码

HashMap的put方法实现：
1、判断key是否已经存在

public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key);
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

2、检查容量是否达到阈值threshold

void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
1
2
3
4
5
6
7
8

3、扩容实现

void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
...
Entry[] newTable = new Entry[newCapacity];
...
transfer(newTable, rehash);
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
1
2
3
4
5
6
7
8
9
10

这里会新建一个更大的数组，并通过transfer方法，移动元素。

void transfer(Entry[] newTable, boolean rehash) {
	int newCapacity = newTable.length;
	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
2
3
4
5
6
7
8
9
10
11
12
13
14
15

第一个for循环是遍历原来的table，第二个while循环用于遍历table中每个位置的链表。也就是如果这次的Entry节点下面有链表，就会执行while循环。
由于JDK7的时候HashMap使用的是头插法，因此先来的数据会在链表尾部，后来的数据在链表头部。其实插入数据的时候是先让要插入节点的next指针指向原有的数据，然后再覆盖掉原有的数据。
例如插入数据的顺序是1,2,3，那么插入完毕之后链表如下所示。

单线程情况：

此时假设我们开始扩容，那么就会执行transfer函数。其中newTable就是扩容后的数组，其大小为原数组的两倍。
我们现在开始外层for循环，现在我们遍历到了3这个Entry了。
由于这个Entry不等于null，所以会执行while语句中的内容。
首先我们的e一开始是3，那么e.next就是2
之后开始进行rehash操作，然后得到hash值之后，我们根据这个hash值在扩容后的HashMap中获取新的插入位置的索引 i。
并且让e（3）的next指针指向这个新数组的索引为i的位置，如下：

之后执行newTable[i]=e这个语句，那么根据头插法，变成如下：

之后执行e=next，也就是让e指针指向2。

然后继续执行while中的逻辑进行头插法操作，就会发现最后的结果是这样子的。

可以发现单线程的情况下执行头插法进行扩容是没有问题的。
移动的逻辑也很清晰，遍历原来table中每个位置的链表，并对每个元素进行重新hash，在新的newTable找到归宿，并插入。（JDK8之后由于只需要两次扰动，因此性能更高，并且元素在newTable的索引要么为原本的索引位置，要么为原索引位置+此次扩容的大小）

多线程情况：

这里假设有两个线程进行扩容方法，那么就是有两个线程进入了resize方法，假设两个线程都执行到了transfer方法，并且两个线程都执行到了下面这一步，在这个时候，如果有一个线程阻塞住了。

if (rehash) {
	e.hash = null == e.key ? 0 : hash(e.key);
}
1
2
3

那么此时的table情况如下：

这两个e其实在线程之间是不互相影响的，他们在各自的线程的私有栈中。
这里假设第一个线程他在运行，另一个线程阻塞，那么第一个线程就会先进行扩容。
然后此时就和单线程扩容情况一样，扩容后如下：

此时线程2醒了，由于线程2的e指针和e.next指向的是3和2，那么由于线程1扩容之后，值没有改变，所以线程2醒来之后的情况如下：

可以发现虽然他们指向的值没有变，但是顺序已经变了，e.next.next=e
而本来应该是e.next=2，e=3这种情况的，所以他们的顺序已经相反了。
然后我们再来一下线程2的扩容：
我们刚才设定从if代码出开始阻塞，那么阻塞结束了继续进行，得到hash值之后获取在newTable中的索引位置。
然后开始第一次插入：
也就是e.next先指向扩容后数组的某个位置



到此第一次循环结束，可以发现好像没有问题，然后我们开始第二次循环：
此时next为3，以为e此时为2，e.next由于一开始倒置的问题变为了3



之后我们第三次进入while循环
此时的e.next就是NULL了，然后再让e.next指向newTable[i]，如下：

此时可以发现已经生成了一个环形了，那么3的next是2 ， 2的next又是3，那么就是无论如何这个e和e.next都在2和3之间跳动了，那么就会导致卡死再这里。
这就是再JDK7下多线程情况下HashMap的并发问题。
他会在扩容的时候从一个链表变成一个环状结构。