⭐ 题目日期：

美团 - 2025/4/4

📝 题解：

JDK 1.7 和 JDK 1.8 在 HashMap 的链表插入方式上的改变（头插法 → 尾插法）主要是为了解决 多线程并发扩容时的死循环问题，同时优化哈希冲突处理逻辑。以下是详细解释：

---

JDK 1.7 的头插法及其问题

1. 头插法实现：
   当发生哈希冲突时，新节点直接插入链表头部（旧链表的头节点会成为新节点的后继节点）。

   // JDK 1.7 的插入逻辑（简化）
   void addEntry(int hash, K key, V value, int bucketIndex) {
       Entry<K,V> e = table[bucketIndex];
       table[bucketIndex] = new Entry<>(hash, key, value, e); // 新节点指向旧头节点
   }

2. 问题根源——并发扩容死循环：

   • 多线程扩容场景：若多个线程同时触发 resize()，在执行链表迁移时，头插法可能导致链表节点指针形成 环形结构。
   • 示例：
     假设线程 A 和线程 B 同时扩容，旧链表为 A → B → null。
     • 线程 A 迁移节点时，将链表反转为 B → A → null（头插法特性）。
     • 线程 B 可能基于旧链表继续操作，最终形成 A → B → A 的循环链表。
   • 后果：后续对该桶的查询操作会陷入死循环，导致 CPU 100%。

---

JDK 1.8 改用尾插法的原因

1. 解决死循环问题：

   • 尾插法实现：新节点插入链表尾部，保持链表原有顺序。

     // JDK 1.8 的插入逻辑（简化）
     Node<K,V> e = table[bucketIndex];
     table[bucketIndex] = new Node<>(hash, key, value, e); // 实际是遍历到尾部插入

   • 避免环形链表：尾插法不会反转链表顺序，即使并发扩容，也不会形成循环结构。

2. 与红黑树优化的协同：

   • JDK 1.8 引入了 红黑树（链表长度 ≥8 且数组容量 ≥64 时树化）。
   • 尾插法保证了链表节点的顺序与插入顺序一致，便于后续树化操作时维护节点关系。

3. 性能优化：

   • 减少遍历成本：头插法每次插入需直接修改头指针，但扩容时需遍历链表反转移位；尾插法在树化后直接操作红黑树，综合性能更优。
   • 内存一致性：尾插法减少了多线程环境下因指令重排序导致的不可预测行为（虽然 HashMap 仍是非线程安全的）。

---

头插法与尾插法对比

特性	头插法（JDK 1.7）	尾插法（JDK 1.8）
插入位置	链表头部	链表尾部
链表顺序	逆序（最后插入的节点在头部）	正序（保持插入顺序）
并发扩容风险	可能形成环形链表，导致死循环	避免环形链表
与红黑树的兼容性	不直接支持树化	顺序一致，便于树化
性能	插入快，但扩容成本高	插入稍慢，但综合性能更优

---

代码示例：头插法导致死循环

以下是一个 JDK 1.7 多线程扩容死循环的简化模拟：

// 初始链表：1 -> 2 -> null
Thread A：迁移节点 1，新链表变为 1 -> null
Thread B：同时迁移节点 2，新链表变为 2 -> 1 -> null
最终结果：链表形成 1 ↔ 2 的循环（Thread B 的尾节点指向 Thread A 的头节点）。

---

总结

• JDK 1.7 头插法：虽然插入高效，但并发扩容时存在严重的死循环问题。
• JDK 1.8 尾插法：
  • 从根本上避免了环形链表的形成，提升了并发环境下的安全性（尽管 HashMap 仍是非线程安全的）。
  • 与红黑树优化结合，进一步提升了哈希冲突处理的性能。
  • 通过保持链表顺序，简化了树化逻辑。

因此，JDK 1.8 改用尾插法是一次针对安全性和性能的综合优化，解决了历史遗留的并发问题。