引言:哈希冲突与 HashMap 的使命
在计算机科学中,哈希表通过哈希函数将 Key 映射到数组下标,实现 O(1) 的查找效率。然而,由于哈希函数输出空间有限,哈希冲突(Hash Collision) 避不可免。
常见的解决冲突方法包括:
- 链地址法(Separate Chaining):HashMap 采用的核心策略。
- 开放定址法(Open Addressing):如线性探测、平方探测。
- 再哈希法(Rehashing):使用多个哈希函数。
- 建立公共溢出区。
HashMap 在单线程环境下表现卓越,但在多线程这片'深水区',它就像一个没有交通灯的十字路口,极易引发致命灾难。
HashMap 的五大线程安全陷阱
多线程同时修改同一个 HashMap 实例时,会引发以下问题:
- 扩容死循环(JDK 1.7):最著名的 Bug,会导致 CPU 飙升至 100%。
- 数据丢失/覆盖(1.7 & 1.8 共有):多个线程同时
put时,由于没有加锁,计算出的索引若相同,后者的值会覆盖前者。 - Size 计算不准:
size++操作非原子性,并发下会导致计数不一致。 - 扩容覆盖(JDK 1.8):多线程同时扩容生成多个新数组,最终只有最后一个线程的数组会被保留,其余线程插入的数据随之丢失。
- 快速失败(Fail-Fast):在迭代过程中若有其他线程修改结构,会立即抛出
ConcurrentModificationException。
深度复现:JDK 1.7 的'死亡之环'
1. 源码现场
JDK 1.7 扩容的核心在于 transfer 方法,其罪魁祸首是头插法(Head Insertion)。
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; // 【关键点 1】记录下一个节点
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i]; // 【关键点 2】头插到新表
newTable[i] = e;
e = next;
} (e != );
}
}
}


