为什么在 Jdk 8 中 HashMap 要转成红黑树？

2026年01月22日

面试考察点

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

对 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 为例）：

// 链表转换为红黑树的阈值
static final int TREEIFY_THRESHOLD = 8;
// 红黑树退化为链表的阈值
static final int UNTREEIFY_THRESHOLD = 6;
// 进行树化的最小表容量，小于此值则优先扩容而非树化
static final int 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 的最佳性能。
常见误区：
1. 误区一： 认为链表长度一超过 8 就立刻树化。
  - 纠正： 还要求当前哈希表的容量（table.length）必须大于等于 MIN_TREEIFY_CAPACITY（默认为 64）。如果容量太小，HashMap 会优先选择扩容（resize） 来分散节点，因为扩容通常更有效。
2. 误区二： 认为红黑树在任何情况下都比链表好。
  - 纠正： 红黑树节点（TreeNode）比链表节点（Node）占用更多内存，且维护成本高。对于非常短（长度<8）的链表，其遍历速度远超红黑树的查找过程。JDK 设置 8 和 6 这两个阈值，正是基于泊松分布统计，在正常良好的哈希函数下，链表长度达到 8 的概率极低（约千万分之六）。这是一种“空间换时间”和“实现复杂度换稳定性”的工程折衷，旨在为极端情况兜底。

总结

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

发布于2026年01月22日|10:24:25