HashMap 的链表插入方式

在 JDK 1.8 之前，HashMap 的链表使用的是 头插法；而在 JDK 1.8 及之后，HashMap 改用了 尾插法。

1. JDK 1.8 之前：头插法

• 方式：新插入的节点会作为链表的头节点，原来的链表节点链接到新节点之后。
• 优点：插入简单，效率高，因为每次只需操作链表的头部，无需遍历链表。
• 缺点：
  • 多线程并发环境中可能导致 环形链表 问题：
    • 如果一个线程在遍历链表时，另一个线程进行插入，可能会因为指针操作不当使链表出现环，从而导致死循环。
  • 影响链表节点的顺序：
    • 头插法会导致后插入的元素排在链表的前面，查询时的顺序与插入顺序相反。

2. JDK 1.8 之后：尾插法

• 方式：新插入的节点会被追加到链表的尾部。
• 优点：
  • 解决了多线程并发问题，不会再产生环形链表。
  • 保证了节点的插入顺序，与插入操作一致，有助于调试和结果可预测性。
• 缺点：插入时需要遍历链表到尾部，性能略低于头插法，但现代 HashMap 的性能优化（如红黑树和负载均衡扩容）使这一点影响很小。

为什么 JDK 1.8 改为尾插法？

1. 线程安全性：

   • 头插法容易在多线程环境下引发链表成环的风险。
   • 虽然 HashMap 本身不是线程安全的，但尾插法设计更稳定，不容易导致隐蔽的 BUG。

2. 插入顺序一致性：

   • 尾插法可以保持链表中元素的插入顺序，调试时数据表现更直观。

3. 红黑树优化的需要：

   • JDK 1.8 引入了链表到红黑树的转换。当链表节点数量超过 8 时，链表会转为红黑树。
   • 如果链表中的顺序紊乱（如头插法带来的逆序），转换效率可能受到影响。

总结

在 JDK 1.8 及以后，HashMap 的链表都使用 尾插法，结合红黑树优化，性能和稳定性都显著提升。