⭐⭐⭐ Spring Boot 项目实战	⭐⭐⭐ Spring Cloud 项目实战
《Dubbo 实现原理与源码解析 —— 精品合集》	《Netty 实现原理与源码解析 —— 精品合集》
《Spring 实现原理与源码解析 —— 精品合集》	《MyBatis 实现原理与源码解析 —— 精品合集》
《Spring MVC 实现原理与源码解析 —— 精品合集》	《数据库实体设计合集》
《Spring Boot 实现原理与源码解析 —— 精品合集》	《Java 面试题 + Java 学习指南》

摘要: 原创出处小哈学Java 「犬小哈」欢迎转载，保留摘要，谢谢！

🙂🙂🙂关注微信公众号：【芋道源码】有福利：

RocketMQ / MyCAT / Sharding-JDBC 所有源码分析文章列表

RocketMQ / MyCAT / Sharding-JDBC 中文注释源码 GitHub 地址

您对于源码的疑问每条留言都将得到认真回复。甚至不知道如何读源码也可以请教噢。

新的源码解析文章实时收到通知。每周更新一篇左右。

认真的源码交流微信群。

面试考察点

面试官提出这个问题，主要想考察以下几个方面：

对 HashMap 核心数据结构的理解： 你是否清楚 JDK 8 之前 HashMap 如何处理哈希冲突，以及该方式在极端情况下的缺陷。
对数据结构（链表与树）的应用与权衡能力： 面试官不仅想知道 “链表转红黑树” 这个事实，更想知道你能否分析链表和红黑树在查找、插入性能上的优劣，以及为什么选择红黑树而不是其他平衡二叉树（如 AVL 树）。
对工程实践和性能优化的洞察： 这道题考察的是面对实际场景中非均匀哈希或恶意碰撞攻击时，如何防止 HashMap 性能从 O(1) 急剧劣化为 O(n)，从而保障系统整体稳定性的设计思路。
对源码细节的掌握程度： 可能延伸出对 TREEIFY_THRESHOLD（树化阈值，值为 8）和 UNTREEIFY_THRESHOLD（退化阈值，值为 6）等具体参数的理解，以及其背后的统计学依据。

核心答案

在 JDK 8 中，HashMap 将哈希冲突时过长的链表转换为红黑树，最核心的目的是为了防止在极端情况下（如哈希函数设计不佳或遭遇恶意碰撞攻击）链表变得过长，从而导致查询、插入等操作的时间复杂度由平均 O(1) 恶化为 O(n)，严重拖累性能。通过转换为红黑树，可以将最坏情况下的时间复杂度优化为 O(log n)，从而保障操作的稳定性。

深度解析

原理/机制

历史方案与问题： 在 JDK 8 之前，HashMap 采用 “数组+链表” 的结构。当多个键（key）的 hashCode() 值映射到同一个数组下标（桶）时，它们会以链表形式存储。在理想情况下，链表很短，遍历开销可忽略。但在哈希函数不均匀或遭遇恶意构造大量哈希冲突的键时，链表会变得非常长，此时 get() 和 put() 操作需要遍历整个链表，性能会急剧下降至 O(n)。
JDK 8 的优化方案： JDK 8 采用了 “数组+链表/红黑树” 的混合结构。当一个桶中的链表长度超过阈值（默认为 8，对应常量 TREEIFY_THRESHOLD），并且当前 HashMap 的容量达到另一个阈值（默认为 64，对应常量 MIN_TREEIFY_CAPACITY）时，该链表就会被转换为一个红黑树。反之，当红黑树中的节点数因删除操作而减少到阈值（默认为 6，对应常量 UNTREEIFY_THRESHOLD）以下时，它会退化为链表。

为什么是红黑树？

这是一个经典的工程权衡问题。

对比链表： 红黑树是一种自平衡的二叉查找树，其查找、插入、删除的最坏时间复杂度均为 O(log n)，这比长链表的 O(n) 要好得多。
对比 AVL 树： 红黑树是近似平衡的，而 AVL 树是严格平衡的。这意味着在频繁的插入和删除操作中，红黑树所需的旋转（再平衡）操作更少，平均性能更高。对于 HashMap 这种可能高频更新（put, remove）的容器，红黑树在维持良好查询性能的同时，减少了维持平衡的开销，是更优的选择。

代码示例与关键常量

我们可以查看 HashMap 源码中的关键逻辑和常量定义（以 OpenJDK 为例）：

// 链表转换为红黑树的阈值
staticfinalint TREEIFY_THRESHOLD = 8;
// 红黑树退化为链表的阈值
staticfinalint UNTREEIFY_THRESHOLD = 6;
// 进行树化的最小表容量，小于此值则优先扩容而非树化
staticfinalint MIN_TREEIFY_CAPACITY = 64;

// 在 putVal 方法中，判断是否要进行树化的逻辑简化示意
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    // ... 省略其他逻辑
    for (int binCount = 0; ; ++binCount) {
        if ((e = p.next) == null) {
            // 在链表尾部插入新节点
            p.next = newNode(hash, key, value, null);
            // 如果链表长度达到树化阈值 - 1（因为binCount从0开始），尝试树化
            if (binCount >= TREEIFY_THRESHOLD - 1)
                treeifyBin(tab, hash);
            break;
        }
        // ... 处理键已存在的情况
    }
    // ...
}

最佳实践与常见误区

最佳实践： 为自己用作 HashMap 键的自定义类实现一个高质量、分布均匀的 hashCode() 方法，这是最根本的预防措施，可以最大程度避免触发树化，发挥 HashMap 的最佳性能。
常见误区：

误区一：认为链表长度一超过 8 就立刻树化。

纠正： 还要求当前哈希表的容量（table.length）必须大于等于 MIN_TREEIFY_CAPACITY（默认为 64）。如果容量太小，HashMap 会优先选择扩容（resize）来分散节点，因为扩容通常更有效。

误区二：认为红黑树在任何情况下都比链表好。

纠正： 红黑树节点（TreeNode）比链表节点（Node）占用更多内存，且维护成本高。对于非常短（长度<8）的链表，其遍历速度远超红黑树的查找过程。JDK 设置 8 和 6 这两个阈值，正是基于泊松分布统计，在正常良好的哈希函数下，链表长度达到 8 的概率极低（约千万分之六）。这是一种“空间换时间”和“实现复杂度换稳定性”的工程折衷，旨在为极端情况兜底。

总结

JDK 8 中 HashMap 引入红黑树，是一种针对哈希冲突极端情况的防御性优化，通过将过长链表的操作复杂度从 O(n) 降至 O(log n)，有效提升了容器的性能稳定性，防止了因哈希碰撞导致的性能灾难。

芋道源码 —— 纯源码解析博客

面试官：为什么在 Jdk 8 中 HashMap 要转成红黑树？