深度剖析 HashMap：从 JDK 1.7 死循环到 1.8 高低位映射优化

引言：哈希冲突与 HashMap 的使命

在计算机科学中，哈希表通过哈希函数将 Key 映射到数组下标，实现 O(1) 的查找效率。然而，由于哈希函数输出空间有限，哈希冲突（Hash Collision） 避不可免。

常见的解决冲突方法包括：

• 链地址法（Separate Chaining）：HashMap 采用的核心策略。
• 开放定址法（Open Addressing）：如线性探测、平方探测。
• 再哈希法（Rehashing）：使用多个哈希函数。
• 建立公共溢出区。

HashMap 在单线程环境下表现卓越，但在多线程这片'深水区'，它就像一个没有交通灯的十字路口，极易引发致命灾难。

---

HashMap 的五大线程安全陷阱

多线程同时修改同一个 HashMap 实例时，会引发以下问题：

1. 扩容死循环（JDK 1.7）：最著名的 Bug，会导致 CPU 飙升至 100%。
2. 数据丢失/覆盖（1.7 & 1.8 共有）：多个线程同时 put 时，由于没有加锁，计算出的索引若相同，后者的值会覆盖前者。
3. Size 计算不准：size++ 操作非原子性，并发下会导致计数不一致。
4. 扩容覆盖（JDK 1.8）：多线程同时扩容生成多个新数组，最终只有最后一个线程的数组会被保留，其余线程插入的数据随之丢失。
5. 快速失败（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 != );
        }
    }
}