为什么 JDK 1.8 对 HashMap 进行了红黑树的改动？

【核心定义】 JDK 1.8 对 HashMap 引入红黑树，本质上是将链表法解决哈希冲突时，链表过长导致的查询性能退化问题，从 O(n) 优化为 O(log n)，从而在极端哈希冲突下保障了 HashMap 的性能下限。

【关键要点】

【深度推导/细节】 核心矛盾：链表查询效率 O(n) 与树结构查询效率 O(log n) 在数据量增大时的性能差距。

逻辑拆解与关键数字解释：

阈值 8：这是链表转树的阈值。这个数字是基于泊松分布的概率统计得出的。在理想的随机哈希情况下，哈希桶中元素数量达到8的概率极低（约小于千万分之六）。因此，在绝大多数正常使用场景下，HashMap 仍以高效的链表形式运行。只有当出现异常或恶意情况时，才会触发树化，这是一种“按需优化”的设计。
退化阈值 6：当红黑树中的节点数因删除操作减少到6时，树会退化为链表。设置一个比8小的退化阈值（6）是为了避免在临界值附近频繁地进行树化和链化，这是一种 hysteresis（滞后）设计，防止不必要的结构转换开销。
最小树化容量 64：即使链表长度达到8，也不会立即树化，还会检查当前哈希表的总容量是否达到 MIN_TREEIFY_CAPACITY（默认64）。如果容量太小，扩容（resize）可能是更优的选择，因为扩容能直接分散冲突的节点。优先扩容可以避免在表很小时就创建复杂的树结构。

树化过程模拟（Step by Step）：

Step 1 - 插入与计数：向 HashMap 插入一个键值对。若发生哈希冲突，元素会被添加到对应桶的链表末尾。同时，该桶的链表长度增加。
Step 2 - 检查树化条件：插入完成后，检查该桶的链表长度是否达到 TREEIFY_THRESHOLD（默认8）。
Step 3 - 容量检查：如果长度达到8，进一步检查当前哈希表 table 的长度是否小于 MIN_TREEIFY_CAPACITY（64）。
- 若小于64，则优先执行 resize() 扩容，尝试通过扩大数组来分散节点。
- 若已大于等于64，则进入树化流程。
Step 4 - 执行树化：遍历当前桶的链表，将 Node 节点转换为 TreeNode 节点，然后调用 treeify 方法，按照红黑树的规则（比较键的哈希值，若哈希值相同则比较 key 的类名和 compareTo 或 System.identityHashCode）构建一棵红黑树。

【关联/对比】

与 JDK 1.7 的对比：JDK 1.7 及之前版本，HashMap 在冲突时只使用单向链表。在遭遇大量哈希冲突时，查询性能会线性下降。1.8 的改动从根本上解决了这一性能瓶颈。
与 ConcurrentHashMap 的关联：JDK 1.8 的 ConcurrentHashMap 也采用了与 HashMap 相似的结构（数组+链表/红黑树），并实现了线程安全的树化操作。这体现了 JDK 在并发集合设计上理念的统一。
与 Hashtable 的对比：Hashtable 通过全表锁保证线程安全，其内部结构在 JDK 1.8 之前也是纯链表，没有红黑树优化。这进一步凸显了 HashMap 1.8 在性能和设计先进性上的优势。

『面试官追问』

直击痛点总结：8、6、64 这三个数字是理解此改动的关键。8 是基于概率统计的性能优化触发点，6 是避免振荡的滞后设计，64 是确保树化有意义的最小全局容量。它们共同构成了一个在空间、时间、稳定性之间取得精妙平衡的工程解决方案。

# 为什么 JDK 1.8 对 HashMap 进行了红黑树的改动？