卡码笔记-最强八股文

# Java中有哪些集合使用红黑树？红黑树有什么特点？

# 简要回答

  1. 直接以红黑树作为核心结构的集合主要有：TreeMap 和 TreeSet。其中TreeSet 本质上是基于TreeMap实现的。
  2. 在特定条件下会用到红黑树的集合有：HashMap、LinkedHashMap、HashSet、LinkedHashSet，以及 ConcurrentHashMap（JDK 1.8+）。它们并不是整体就是红黑树，而是在哈希冲突严重时，会把桶中的链表树化成红黑树。
  3. 红黑树是一种自平衡二叉查找树。不追求绝对平衡，但能保证树的高度始终维持在对数级别，因此查找、插入、删除的时间复杂度都能稳定在 O(logN) 。

# 详细回答

# 哪些集合使用红黑树

  1. TreeMap ：
    • TreeMap的底层就是红黑树。
    • 它会按照key的自然顺序或自定义比较器进行排序。
    • 因为底层是红黑树，所以 put()、get()、remove() 的时间复杂度都是 O(logN) 。
    • 它适合需要排序、范围查询、获取最小值/最大值的场景，比如 firstKey()、lastKey()、subMap()。
  2. TreeSet ：
    • TreeSet的底层本质上是TreeMap，因此它同样依赖红黑树。
    • 它的元素默认按照自然顺序排序，也可以在创建时传入Comparator自定义排序规则。
    • TreeSet适合去重 + 排序同时存在的场景。
  3. HashMap（JDK 1.8+） ：
    • HashMap的底层是数组 + 链表 / 红黑树。
    • 正常情况下，桶中元素是链表；当链表长度达到树化阈值 TREEIFY_THRESHOLD（默认 8），并且数组容量达到最小树化容量 MIN_TREEIFY_CAPACITY（默认 64） 时，链表会被转换为红黑树。
    • 当树中节点数量减少到 6 时，又会退化回链表。
  4. LinkedHashMap（JDK 1.8+） ：
    • LinkedHashMap继承自HashMap，底层同样可能出现链表树化。
    • 它比HashMap多维护了一条双向链表，用于保持插入顺序或访问顺序。它既可能在桶中使用红黑树，又能在整体上保持有序迭代。
  5. HashSet 和 LinkedHashSet ：
    • HashSet的底层是HashMap，所以在JDK 1.8+中，发生严重哈希冲突时，桶中也可能树化为红黑树。
    • LinkedHashSet的底层可以看作LinkedHashMap，同样也可能在桶内使用红黑树。
    • 需要注意，它们使用红黑树只是底层实现细节，并不代表集合整体具有排序能力。
  6. ConcurrentHashMap（JDK 1.8+） ：
    • ConcurrentHashMap在JDK 1.8+中的底层也是数组 + 链表/红黑树。
    • 当某个桶中的链表过长时，也会树化，以降低极端冲突下的查询成本。
    • 它和HashMap的区别在于，ConcurrentHashMap还要同时解决并发安全问题。

# 红黑树的特点

  1. 二叉查找树：
    • 左子树节点值小于当前节点，右子树节点值大于当前节点。因此红黑树天然支持有序遍历、范围查找、最值查找。
  2. 自平衡树：
    • 红黑树会通过旋转 + 变色来维持平衡。
    • 它并不要求每一层都完全平衡，但能保证不会退化成一条长链表。
  3. “弱平衡”结构：
    • 红黑树要求从任意节点到所有叶子节点的每条路径上，黑色节点数量相同。同时，红色节点不能连续出现。
    • 这使得红黑树的最长路径不会超过最短路径的 2 倍，所以整体高度依然是 O(logN) 。
  4. 查找、插入、删除性能稳定：
    • 查找时间复杂度是 O(logN) 。
    • 插入时间复杂度是 O(logN) 。
    • 删除时间复杂度也是 O(logN) 。
    • 这也是 TreeMap、TreeSet 和 HashMap 树化后能保持稳定性能的原因。
  5. 插入和删除时调整成本比 AVL 树更低：
    • 红黑树不像 AVL 树那样追求“绝对平衡”，所以在频繁插入、删除时，旋转次数通常更少。这也是 Java 集合框架更偏向选择红黑树而不是 AVL 树的重要原因。
  6. 查询极致性能不如更严格平衡的树：
    • 因为红黑树是“弱平衡”，所以它的查询效率理论上会略逊于 AVL 树。但综合插入、删除、维护成本后，它在工程上通常是更划算的选择。

# 知识图解

  1. 红黑树结构 image
  2. ConcurrentHashMap使用红黑树解决哈希冲突

# 知识拓展

# 面试官可能的追问

  1. 为什么TreeMap和 TreeSet直接使用红黑树，而HashMap只是冲突严重时才树化？
    • 因为 TreeMap 和 TreeSet 的目标本来就是保持有序，所以适合使用红黑树。
    • HashMap 的核心目标则是通过哈希快速定位桶，理想情况下平均复杂度是 O(1) 。只有在冲突严重、链表过长时，才需要用红黑树兜底，把最坏情况从 O(N) 优化到 O(logN) 。
  2. 为什么 Java 集合里更常用红黑树，而不是 AVL 树？
    • AVL 树平衡更严格，查询会更快一点，但插入和删除时需要更频繁地旋转，维护成本更高。
    • 红黑树虽然不是绝对平衡，但已经足够保证 O(logN) 的性能，而且插入、删除调整更少，更适合像 TreeMap、TreeSet 这种需要频繁修改的数据结构。
  3. HashMap 树化后是不是就变成有序集合了？
    • 不是。HashMap 中的红黑树只存在于单个桶内部，目的是优化冲突桶的查找效率。
    • 整个 HashMap 依然是无序的，它不会像 TreeMap 或 TreeSet 那样提供全局排序能力。
Last Updated: 4/30/2026, 11:54:17 AM

← Error和Exception的区别？ →

评论

验证登录状态...