前言
前两天在公司的内部博客看到一个同事分享的线上服务挂掉CPU100%的文章，让我联想到HashMap在不恰当使用情况下的死循环问题，这里做个整理和总结，也顺便复习下HashMap。
直接上测试代码
由于机器配置和性能不同，测试出效果的线程数和put数量也各不相同
public class HashMapInfiniteLoopTest {
/**
* 基于JDK1.7测试HashMap在多线程环境下假死锁的情况
* JDK1.8的HashMap实现跟1.7比较已经有很大的变化，已不存在这样的问题
* （其实这本来不是JDK的一个问题，HashMap本就不是线程安全的，多线程环境下共享一定要用线程安全的Map容器）
*/
public static void main(String[] args) {
String jdkVer = System.getProperty("java.version"); //JDK版本
String jdkMod = System.getProperty("sun.arch.data.model"); //32位还是64位
System.out.println(jdkVer +"#"+ jdkMod);
final Map<String, String> map = new HashMap<>();
// final Map<String, String> map = new ConcurrentHashMap<>();
for(int i=0; i<30; i++) {
new Thread(new Runnable() {
@Override
public void run() {
System.out.println(Thread.currentThread().getName());
for(int j=0; j<1000; j++) {
map.put(""+j+"_"+System.currentTimeMillis(), ""+j+"_"+System.currentTimeMillis());
}
}
}, "myThread_"+i).start();
}
}
}
通过jconsole查看Java进程情况：
最后只能强制结束进程
分析
HashMap使用hash表来作为其底层存储的数据结构（数组下标实现快速索引，链表实现元素碰撞处理），并且支持动态扩容，主要通过resize方法实现，也是从这个方法开始出问题的。（这里有两个面试官喜欢问的点:1.table的默认长度以及扩容前后大小？2.为什么要求table的长度必须是2的N次方？）
因为整个HashMap都不是线程安全的，所以JDK也未对resize方法做同步，如果错误的在多线程环境下共享访问了HashMap就有可能引起我前面提到的假死锁问题。动态扩容的时候需要把旧的链表迁移到新的hash表中，如果是在多线程环境下，可能会形成循环链表，在再次put遍历每个链表检查是否存在相同key时，死循环就出现了（如果是get也会有同样的情况）。
下面是我整理转载自https://coolshell.cn/articles/9606.html的部分内容（写得太好了）：
|
1
2
3
4
5
6
7
8
9
10
11
12
|
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);
} |
迁移的源代码，注意高亮处：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
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);
}
}
} |
- 假设我们的hash算法就是简单的用key mod 一下表的大小（也就是数组的长度）。
- 最上面的是old hash 表，其中的Hash表的size=2, 所以key = 3, 7, 5，在mod 2以后都冲突在table[1]这里了。
- 接下来的三个步骤是Hash表 resize成4，然后所有的<key,value> 重新rehash的过程
并发下的Rehash
1）假设我们有两个线程。我用红色和浅蓝色标注了一下。
我们再回头看一下我们的 transfer代码中的这个细节：
|
1
2
3
4
5
6
7
|
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);
|
而我们的线程二执行完成了。于是我们有下面的这个样子。
注意，因为Thread1的 e 指向了key(3)，而next指向了key(7)，其在线程二rehash后，指向了线程二重组后的链表。我们可以看到链表的顺序被反转后。
2）线程一被调度回来执行。
- 先是执行 newTalbe[i] = e;
- 然后是e = next，导致了e指向了key(7)，
- 而下一次循环的next = e.next导致了next指向了key(3)
3）一切安好。
线程一接着工作。把key(7)摘下来，放到newTable[i]的第一个，然后把e和next往下移。
4）环形链接出现。
e.next = newTable[i] 导致 key(3).next 指向了 key(7)
注意：此时的key(7).next 已经指向了key(3)， 环形链表就这样出现了。
于是，当我们的线程一调用到，HashTable.get(7)时，悲剧就出现了——Infinite Loop。
总结
多线程并发环境下访问共享的map时一定要用线程安全的Map容器，如ConcurrentHashMap，HashTable等。