前言
前两天在公司的内部博客看到一个同事分享的线上服务挂掉 CPU100% 的文章，让我联想到 HashMap 在不恰当使用情况下的死循环问题，这里做个整理和总结，也顺便复习下 HashMap。
直接上测试代码
由于机器配置和性能不同，测试出效果的线程数和 put 数量也各不相同
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
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 map = ``new HashMap<>();
// final Map 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 e = src[j];
if (e != null``) {
src[j] = null``;
do {
Entry 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，然后所有的 重新 rehash 的过程
并发下的 Rehash
1）假设我们有两个线程。我用红色和浅蓝色标注了一下。
我们再回头看一下我们的 transfer 代码中的这个细节：
|
1
2
3
4
5
6
7
|
do {
Entry 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 等。
欢迎来到这里！
我们正在构建一个小众社区，大家在这里相互信任，以平等 • 自由 • 奔放的价值观进行分享交流。最终，希望大家能够找到与自己志同道合的伙伴，共同成长。
注册 关于