" />
文章

HashMap 的链表为什么要转换成红黑树？

Posted recently Updated recently
By Administrator
12~15 min read

HashMap 的链表为什么要转换成红黑树？

面试指北 · 淘天

题意

面试官问的是：JDK 8 的 HashMap 为什么要在某个桶的链表达到一定长度后，把链表转成红黑树？这题表面在问“链表和红黑树的区别”，实际想考察三点：

  1. HashMap 在哈希冲突严重时，性能会怎样退化；
  2. 红黑树相比链表解决了什么问题；
  3. 为什么不是一开始就用红黑树，以及树化有哪些前提条件。

回答时不能只背“链表长度到 8 就转红黑树”，还要讲清楚链表在极端冲突下会从平均 O(1) 退化为 O(n)，红黑树用 O(log n) 做兜底，同时说明树化是有成本的，所以只在必要时才升级。

结论

一句话总结：JDK 8 把过长链表转成红黑树，是为了在大量哈希冲突的极端场景下，把桶内查找、插入、删除的最坏时间复杂度从 O(n) 降到 O(log n)，防止 HashMap 因链表过长而严重退化。

但要补充两个限定：

  • 不是所有链表都会树化。默认要满足桶内链表达到阈值 TREEIFY_THRESHOLD = 8，并且 table 容量至少达到 MIN_TREEIFY_CAPACITY = 64；容量不够时优先扩容，而不是立刻树化。
  • 红黑树只是冲突桶的“兜底结构”。正常情况下哈希分布较均匀，大多数桶只有 0 或 1 个元素，链表更简单、内存更省，因此 HashMap 不会一开始就用红黑树。

要点展开

1. 链表桶在严重冲突下会退化为 O(n)

HashMap 的平均 O(1) 查询建立在“哈希函数把 key 均匀分散到各个桶”这个前提上。正常情况下，一个桶里元素很少，查找时先定位桶，再比较桶内少量节点，速度很快。

但如果发生大量哈希冲突，大量 key 被映射到同一个桶，桶内就会形成很长的链表。此时查找、插入、删除都要沿着链表逐个比较，最坏时间复杂度退化为 O(n)。极端情况下，如果攻击者能构造大量相同哈希值的 key，还可能造成哈希碰撞攻击，让 HashMap 的性能急剧下降。

JDK 8 之前，桶内冲突元素只用单向链表串联；JDK 8 引入红黑树，就是为了给这种极端情况加一层性能保护。

2. 红黑树把最坏情况降到 O(log n)

红黑树是一种近似平衡的二叉搜索树，能够保证查找、插入、删除在最坏情况下为 O(log n)。当桶内链表过长时，把链表替换成红黑树，即使冲突很严重，也不会退化成 O(n) 的线性遍历。

可以这样理解：

  • 链表：桶内元素越多，平均比较次数越多，最坏 O(n)；
  • 红黑树：通过旋转和染色维持近似平衡，最坏 O(log n)。

但红黑树不是没有代价的。TreeNode 比普通 Node 占用更多内存，插入、删除时还要维护树结构，可能涉及旋转和染色。因此它适合作为“冲突严重时”的优化手段，而不是默认结构。

JDK 8 中相关判断可以简化理解为：

// JDK 8 HashMap 中桶内查找的简化逻辑
if (first instanceof TreeNode) {
    return ((TreeNode<K, V>) first).getTreeNode(hash, key);
}
// 否则按链表遍历

也就是说，只有当前桶已经树化，才会走红黑树查找；普通桶仍然走链表。

3. 为什么阈值默认是 8，而不是更小？

这个 8 不是随便定的，核心是概率与成本的折中。

在理想哈希分布、默认负载因子 0.75 的情况下，桶内节点数近似服从泊松分布。源码注释中给出的数量级是：桶内节点数达到 8 的概率非常低，大约千万分之一。也就是说，正常使用 HashMap 时，链表长度达到 8 本身就很少见；一旦达到，往往说明哈希分布已经比较糟糕，值得升级为红黑树。

所以 8 的设计意图是：让绝大多数正常桶继续使用轻量链表，只把红黑树的复杂度和内存开销留给极少数异常冲突的桶。

4. 树化不是无条件的：8 和 64 要一起看

树化的常见前提有两个：

  1. 桶内链表节点数达到 TREEIFY_THRESHOLD，默认是 8；
  2. HashMap 的 table 容量达到 MIN_TREEIFY_CAPACITY，默认是 64。

如果链表已经很长，但数组容量还小于 64，HashMap 会优先调用 resize() 扩容，而不是马上树化。原因是容量较小时，冲突可能只是“桶太少”导致的；扩容后重新散列，节点有机会被分散到更多桶里，这通常比直接构建红黑树更划算。

简化后的逻辑类似：

// JDK 8 HashMap#treeifyBin 的关键分支（简化）
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) {
    resize(); // 容量不足 64，优先扩容
} else if ((e = tab[index]) != null) {
    // 将链表节点替换为 TreeNode，并构建红黑树
}

另外，树化后如果节点减少，也可能退化回链表。JDK 8 中还有 UNTREEIFY_THRESHOLD = 6：当树节点少到一定程度时，会重新转回普通链表。6 和 8 之间留出缓冲，是为了避免在边界附近反复“树化—退化”，减少不必要的结构转换开销。

5. 为什么不干脆所有桶都用红黑树？

因为大多数桶根本不需要红黑树。HashMap 的核心优势是哈希定位后的 O(1) 平均访问，正常桶里通常只有少量节点，链表遍历几次就结束了，实现简单、内存占用小，CPU 缓存局部性也更好。

如果所有桶都用红黑树，会带来几个问题：

  • 每个节点要维护树指针、颜色等信息，内存开销更大；
  • 插入、删除要维护平衡，常数开销更高；
  • 大多数短链表场景下，红黑树并不会比链表快，反而更重。

所以 HashMap 的策略是：常态用链表，极端冲突用红黑树兜底。这也体现了工程上的折中思想，而不是单纯追求理论上的最坏复杂度。

易错点与对比

易错点 正确理解
“链表长度一到 8 就立刻转红黑树” 不准确。达到阈值只是“尝试树化”，还要看 table 容量是否达到 64；容量不足时优先扩容。
“8 是退化阈值” 8 是树化阈值，退化回链表的阈值默认是 6，二者不是同一个概念。
“树化后整个 HashMap 都变成 O(log n)” 树化只发生在冲突严重的桶上，整体平均仍然是 O(1)，只是最坏情况被优化到 O(log n)。
“红黑树全面优于链表” 短链表更轻量、更简单；红黑树有额外内存和维护成本，只适合长冲突桶。
“树化能解决并发问题” 不能。HashMap 本身不是线程安全的，树化只优化单线程下的冲突性能。
“HashMap 树化后像 TreeMap 一样有序” 不是。HashMap 不保证顺序，桶内红黑树只是为了高效查找，不是全局有序结构。

还可以对比一下红黑树和 AVL 树：AVL 更严格平衡，查找可能略快，但插入删除时旋转更多；红黑树平衡要求稍宽松，插入删除的综合维护成本更低，更适合 HashMap 这种既有查询又有频繁修改的场景。

小结

HashMap 在 JDK 8 中引入“链表转红黑树”，本质是为了解决严重哈希冲突下链表退化为 O(n) 的问题。红黑树能把冲突桶的查找、插入、删除最坏复杂度降到 O(log n)，从而提升极端场景下的稳定性。

但树化不是默认开启的“全能优化”：它需要满足阈值 8 和容量 64 等条件，容量不足时优先扩容；正常短链表仍然更轻量。面试回答时，建议按“链表退化的原因 → 红黑树的 O(log n) 兜底 → 8 和 64 的触发条件 → 为什么不全用红黑树”这条线展开，既回答原因，也体现对工程折中的理解。

面试指北
License:  CC BY 4.0