请说明 JDK 1.8 中 HashMap 引入红黑树的原因及其带来的影响。

回答思路

1. 【回答框架 1】JDK 1.8 之前 HashMap 采用数组加链表，当哈希冲突严重时链表过长，查询时间复杂度退化为 O(n)。为解决该问题，JDK 1.8 在链表长度超过阈值（默认 8）且数组容量不小于 64 时，将链表转换为红黑树。
2. 【回答框架 2】红黑树是一种自平衡二叉查找树，保证最坏情况下查找、插入、删除的时间复杂度为 O(log n)，显著提升冲突严重时的性能。此外，红黑树相比 AVL 树旋转操作更少，在频繁插入删除的场景下效率更高。
3. 【回答框架 3】引入红黑树是空间与时间的权衡：树节点占用空间约为普通节点的两倍，因此只有在链表长度达到阈值时才转换，并在扩容或树节点减少时（低于 6）会转换回链表，以节省空间。
4. 【回答框架 4】JDK 1.8 还改进了扩容机制，避免 1.7 中的头插法造成死循环，但这与红黑树改动是两项独立优化。
5. 【关键点 1】JDK 1.8 前 HashMap 最坏 O(n)，红黑树将最坏降至 O(log n)。
6. 【关键点 2】链表长度超过 8 且数组容量大于等于 64 时树化。
7. 【关键点 3】树节点内存开销大，树退化阈值（6）低于树化阈值（8）避免频繁转换。
8. 【关键点 4】红黑树自平衡保证性能稳定，适合高冲突场景。
9. 【易错点 1】误认为树化阈值 8 是固定不变的，实际还需数组容量条件。
10. 【易错点 2】忽略红黑树与链表转换的动态平衡，可能误解性能始终最优。
11. 【易错点 3】将 HashMap 线程安全问题与红黑树改动混淆。