深度剖析 HashMap：从 JDK 1.7 死循环到 1.8 高低位映射优化
1. JDK 1.7 的死循环问题
在 JDK 1.7 中，HashMap 采用数组 + 链表结构，扩容时使用头插法迁移节点。当多线程并发扩容时，可能导致链表节点形成环形结构，触发死循环。
问题复现：
- 线程 A 和 B 同时扩容，均指向同一链表。
- 线程 A 执行
Entry<K,V> next = e.next;后挂起。 - 线程 B 完成扩容，链表节点顺序反转（头插法特性）。
- 线程 A 恢复执行，将反转后的节点重新插入，形成环状链表： $$e_1 \rightarrow e_2 \rightarrow e_1$$
2. JDK 1.8 的优化策略
2.1 数据结构升级
- 链表 → 红黑树：当链表长度 ≥ 8 且数组长度 ≥ 64 时，链表转为红黑树，将查询复杂度从 $O(n)$ 降至 $O(\log n)$。
- 尾插法取代头插法：扩容时保持节点顺序，避免环形链表。
2.2 高低位映射优化
JDK 1.8 通过高位异或运算优化哈希冲突，核心公式： $$ \text{index} = (n - 1) & \left( \text{hash} \oplus (\text{hash} \gg 16) \right) $$优化原理：
- 高位参与运算：将哈希值的高 16 位与低 16 位异或，使高位变化影响索引分布。
- 降低碰撞概率：避免因数组长度 $n$ 较小（如 $2^k$）时，低位重复导致的哈希聚集。
3. 扩容机制对比
| 特性 | JDK 1.7 | JDK 1.8 |
|---|---|---|
| 数据结构 | 数组 + 链表 | 数组 + 链表/红黑树 |
| 插入方式 | 头插法（易成环） | 尾插法（防环） |
| 哈希计算 | hash % n | (n-1) & (hash ^ (hash >>> 16)) |
| 扩容触发 | 先插入后检查 | 先检查后插入 |
4. 关键源码解析（JDK 1.8）
final V putVal(int hash, K key, V value) { // 检查是否需扩容 if (++size > threshold) resize(); // 计算索引 int index = (n - 1) & (hash ^ (hash >>> 16)); // 尾插法插入节点 if (bin == null) tab[index] = newNode(...); else { // 链表或红黑树插入逻辑 } }5. 性能影响
- 并发安全：尾插法解决死循环，但非线程安全，仍需
ConcurrentHashMap。 - 查询效率：红黑树优化极端哈希冲突场景。
- 哈希均匀性：高低位映射使索引分布更均匀，减少碰撞。
总结
JDK 1.8 的 HashMap 通过高低位映射和数据结构升级，显著提升了并发安全性与查询效率。理解其底层机制，有助于规避开发中的潜在问题，并优化高性能场景下的数据结构选型。
