好的，我们开始今天的讲座。
主题：JAVA HashMap在高并发场景造成死循环CPU 100%的底层原因解析
大家好，今天我们来深入探讨一个Java开发中经常遇到的，而且比较棘手的问题：在高并发环境下，HashMap可能导致的死循环和CPU 100%占用。这个问题曾经让很多开发者头疼不已，理解其底层原因对于我们编写健壮的并发程序至关重要。
一、HashMap的基本原理回顾
首先，我们快速回顾一下HashMap的基本工作原理。HashMap是一种基于哈希表实现的键值对存储结构。它的核心在于使用键的哈希值来快速定位到存储位置。
- 哈希函数： HashMap使用哈希函数将键转换为一个整数，这个整数就是哈希码(hashCode)。理想情况下，不同的键应该产生不同的哈希码，但这很难保证，因此会发生哈希冲突。
- 数组+链表（或红黑树）： HashMap内部维护一个数组，数组的每个元素称为一个桶(bucket)。当发生哈希冲突时，多个键值对会被存储在同一个桶中，通常以链表的形式组织。在JDK 1.8之后，当链表长度超过一定阈值（默认为8）时，链表会被转换为红黑树，以提高查找效率。
- put操作： 当我们向HashMap中插入一个键值对时，HashMap会首先计算键的哈希码，然后根据哈希码找到对应的桶。如果桶是空的，则直接插入。如果桶中已经有元素，则需要遍历链表（或红黑树），如果找到相同的键，则更新值；否则，将新的键值对添加到链表（或红黑树）的末尾。
- get操作： get操作类似，根据键的哈希码找到对应的桶，然后遍历链表（或红黑树），查找对应的键，如果找到则返回对应的值，否则返回null。
- resize操作： 当HashMap中的元素数量达到一定的阈值（负载因子 * 容量）时，HashMap会进行扩容(resize)。扩容会创建一个新的数组，大小是原来的两倍，然后将所有元素重新哈希到新的数组中。这个过程称为rehash。
下面是一个简单的HashMap put操作的示例代码：
import java.util.HashMap;
public class HashMapExample {
public static void main(String[] args) {
HashMap<String, Integer> map = new HashMap<>();
map.put("apple", 1);
map.put("banana", 2);
map.put("cherry", 3);
System.out.println(map.get("banana")); // Output: 2
}
}二、死循环的根源：并发下的rehash
HashMap在单线程环境下工作良好。但是，在高并发环境下，当多个线程同时进行put操作，并且触发了resize操作时，就可能发生死循环。这是因为rehash过程不是线程安全的。
具体来说，问题出现在多线程并发地对一个链表进行rehash时。假设有两个线程A和B同时对HashMap进行put操作，并且都触发了resize操作。
- 两个线程都开始rehash： 两个线程都会创建一个新的数组，大小是原来的两倍。
- 线程A先完成rehash： 线程A先完成了rehash操作，将所有元素都移动到了新的数组中。
- 线程B开始rehash： 此时，线程B也开始rehash操作，但是它使用的是线程B自己的旧数组的引用。如果此时线程B的旧数组中的某个桶上存在一个链表，并且这个链表中的两个节点的next指针在rehash后指向了彼此，那么就会形成一个环。
- 死循环： 当后续的get操作或者put操作访问到这个桶时，就会陷入死循环，因为会一直在这个环中遍历。
三、代码示例和模拟
为了更好地理解这个问题，我们来看一个简化的代码示例，模拟HashMap的rehash过程，并展示死循环是如何产生的。
import java.util.HashMap;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
public class HashMapDeadLoop {
static final int SIZE = 2; // 简化容量，方便模拟
static Map<Integer, String> map = new HashMap<>(SIZE);
public static void main(String[] args) throws InterruptedException {
// 确保hash碰撞
map.put(5, "A"); // 5 % 2 = 1
map.put(9, "B"); // 9 % 2 = 1
map.put(13, "C"); // 13 % 2 = 1
System.out.println("Initial map: " + map);
Thread t1 = new Thread(() -> {
for (int i = 0; i < 10000; i++) {
map.put(i, "Thread1-" + i); // 触发resize
}
});
Thread t2 = new Thread(() -> {
for (int i = 10000; i < 20000; i++) {
map.put(i, "Thread2-" + i); // 触发resize
}
});
t1.start();
t2.start();
t1.join();
t2.join();
System.out.println("Final map size: " + map.size());
}
}这个例子中，我们故意使用小的容量(SIZE=2)并插入一些键，使得它们在初始状态下发生哈希冲突，都在同一个桶中。然后，我们启动两个线程，分别向HashMap中插入大量的键值对，这会强制HashMap进行多次resize操作。在高并发下，很容易触发上述的死循环问题。
需要注意的是，在实际运行中，死循环的发生是随机的，不容易复现。但是，通过增加线程数量和插入数据的量，可以增加复现的概率。
四、JDK 1.7 的源码分析
为了更深入地理解这个问题，我们来看看JDK 1.7中HashMap的resize方法的源码（简化版）：
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
transfer(newTable);
table = newTable;
threshold = (int) (newCapacity * loadFactor);
}
void transfer(Entry[] newTable) {
Entry[] src = table;
int newCapacity = newTable.length;
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); // 关键：重新计算hash
e.next = newTable[i];
newTable[i] = e;
e = next;
} while (e != null);
}
}
}- resize(): 创建一个新的Entry数组，然后调用
transfer()方法将旧数组中的元素迁移到新数组中。 - transfer(): 遍历旧数组的每个桶，然后遍历每个桶中的链表。对于链表中的每个元素，重新计算其在新数组中的位置，然后将其插入到新数组的对应位置。
问题就出在 transfer() 方法中。假设有两个线程A和B同时执行 transfer() 方法。
- 初始状态： 假设线程A和线程B都拿到同一个链表，链表中有两个元素A和B，A.next = B, B.next = null。
- 线程A执行： 线程A先执行，假设A和B经过rehash后仍然在同一个桶中。线程A会按照链表的顺序，依次将A和B插入到新数组中。执行完之后，A.next = null, B.next = A。
- 线程B执行： 线程B也开始执行，但是它仍然持有旧链表的引用。线程B也会按照链表的顺序，依次将A和B插入到新数组中。但是，由于线程A已经修改了链表的结构，线程B在执行时可能会出现问题。例如，如果线程B先处理B，然后处理A，那么就会形成一个环：A.next = B, B.next = A。
五、JDK 1.8 的改进
JDK 1.8对HashMap进行了很多改进，其中一个重要的改进是解决了并发下的死循环问题。JDK 1.8使用了一种新的rehash方法，它避免了在链表头部插入元素，而是保持了链表的原始顺序。
JDK 1.8的源码（简化版）：
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
// ... (省略计算newCap和newThr的代码)
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}关键在于 preserve order 部分。JDK 1.8 将链表拆分成两个链表：loHead 和 hiHead。loHead 链表中的元素的哈希值与旧容量进行与运算的结果为0，hiHead 链表中的元素的哈希值与旧容量进行与运算的结果不为0。然后，将loHead 链表放在新数组的原始位置，将hiHead 链表放在新数组的原始位置加上旧容量的位置。
这样做的目的是保持链表中元素的相对顺序不变，从而避免了死循环的发生。虽然JDK 1.8解决了死循环的问题，但是HashMap仍然不是线程安全的。在高并发环境下，仍然可能出现数据丢失等问题。
六、解决方案：使用线程安全的Map
既然HashMap不是线程安全的，那么在高并发环境下，我们应该使用线程安全的Map。Java提供了多种线程安全的Map实现，最常用的有以下几种：
- ConcurrentHashMap： ConcurrentHashMap是Java并发包(java.util.concurrent)中提供的一个线程安全的HashMap实现。它使用了分段锁(Segment)机制，将整个Map分成多个段，每个段拥有自己的锁。这样，多个线程可以同时访问不同的段，从而提高了并发性能。
- Collections.synchronizedMap： Collections.synchronizedMap方法可以将一个普通的HashMap包装成一个线程安全的Map。它使用了synchronized关键字来保证线程安全，因此性能相对较低。
- Hashtable： Hashtable是Java早期版本中提供的线程安全的Map实现。它使用了synchronized关键字来保证线程安全，因此性能较低。并且Hashtable 不允许键或值为 null。
下面是一个使用ConcurrentHashMap的示例代码：
import java.util.concurrent.ConcurrentHashMap;
public class ConcurrentHashMapExample {
public static void main(String[] args) throws InterruptedException {
ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>();
Thread t1 = new Thread(() -> {
for (int i = 0; i < 10000; i++) {
map.put("key-" + i, i);
}
});
Thread t2 = new Thread(() -> {
for (int i = 10000; i < 20000; i++) {
map.put("key-" + i, i);
}
});
t1.start();
t2.start();
t1.join();
t2.join();
System.out.println("Final map size: " + map.size());
}
}在高并发环境下，ConcurrentHashMap是首选的线程安全Map实现。因为它具有较高的并发性能，并且提供了丰富的功能。
| 实现方式 | 线程安全性 | 性能 | 是否允许null键/值 |
|---|---|---|---|
| HashMap | 不安全 | 高 | 允许 |
| ConcurrentHashMap | 安全 | 较高 | 不允许null键 |
| Collections.synchronizedMap | 安全 | 较低 | 允许 |
| Hashtable | 安全 | 低 | 不允许 |
七、总结：避免HashMap并发问题
HashMap在并发场景下可能导致死循环和CPU 100%占用，根源在于resize时的rehash过程不是线程安全的。JDK 1.8虽然解决了死循环问题，但HashMap仍然不是线程安全的。在高并发环境下，应该使用线程安全的Map实现，如ConcurrentHashMap。选择合适的线程安全Map是保证并发程序正确性和性能的关键。