💡 为什么要转红黑树？一句话总结

平时大家哈希冲突少，HashMap 像个整齐的抽屉，拿东西都是“一拿一个准”（时间复杂度 $O(1)$）。

但如果遇到极端情况（比如被人恶意攻击），所有数据都挤在同一个抽屉里连成了一条长长的“无尽链表”，这时候想找个东西就得从头翻到尾（时间复杂度退化成 $O(n)$），系统就会卡死。

这时候引入红黑树，就是为了给 HashMap 做“极端情况的保底方案”。

🔍 链表 vs 红黑树：大型找人现场

假设某个抽屉里倒霉地挤了 10万个 数据：

• 如果用链表： 你要找最后一个人，得按顺序把前面 99999 个人都问一遍（最坏问 10 万次），CPU 直接烧冒烟。
• 如果用红黑树： 红黑树是个“大分叉树”，它会把数据均匀平衡地张开。找人时每次都能砍掉一半的范围（时间复杂度 $O(\log n)$）。10万个数据，你最多只需要问 17 次就能找到！

这就是为什么换成红黑树后，极端情况下的性能能暴涨几千倍。

🚧 什么时候会触发“变成红黑树”？

HashMap 也是个精明人，树化（变红黑树）是要消耗额外空间的，所以它设置了两个硬性指标（必须同时满足）：

1. 链表长度达到 8： 某个抽屉里排队的人大于等于 8 个了，说明冲突有点严重。
2. 总容量达到 64： 整个 HashMap 的大阵仗至少有 64 个槽位了。

⚠️ 注意（面试必考）： 如果链表长度到了 8，但总容量还不到 64，HashMap 会觉得“地方还小呢，没必要整红黑树这么高级的玩意”，它会选择直接扩容，把数据强行分流到新位子上。