红黑树在工程中有哪些典型应用？为什么 HashMap 用它？

简化版

红黑树因为「增删查都稳定 O(log n)、维护成本低」，被大量用作有序容器和索引结构：Java 的 TreeMap/TreeSet、HashMap（链表过长时转红黑树）、C++ STL 的 map/set、Linux 内核的进程调度（CFS）、内存管理、epoll、Nginx 定时器等。HashMap 用它，是为了在哈希冲突严重、链表退化时，把桶内查找从 O(n) 降到 O(log n)，抵御哈希碰撞攻击。

详细版

Java

TreeMap / TreeSet：底层就是红黑树，提供按 key 有序的映射/集合，支持范围查询、firstKey、ceilingKey、floorKey 等有序操作。
HashMap（JDK 8+）：当某个桶的链表长度 ≥ 8 且数组容量 ≥ 64 时，链表转成红黑树，把最坏查找从 O(n) 降到 O(log n)。

C++ STL

std::map / std::set / multimap / multiset 通常都用红黑树实现，保证有序 + O(log n)。

操作系统 / 中间件

Linux 完全公平调度器（CFS）：用红黑树按进程的 vruntime 排序，每次 O(log n) 取最小（最该运行的进程）。
Linux 内存管理：虚拟内存区域（VMA）用红黑树组织，便于按地址查找。
epoll：内核用红黑树管理被监听的文件描述符。
Nginx：定时器用红黑树。

完整版教学

一、红黑树适合做什么

红黑树的卖点是「在频繁增删的同时，保证查找、插入、删除都稳定 O(log n)，且更新成本低、天然有序」。这让它成为「需要有序、又要频繁动态更新」场景的默认选择：

需要按 key 排序、支持范围查询、找前驱后继 → 哈希表做不到（无序），红黑树可以。
需要最坏情况有保证（不能退化）→ 普通 BST 会退化，红黑树不会。

二、TreeMap / TreeSet：有序映射的代表

TreeMap 用红黑树，所以它的 key 始终有序。这带来哈希表没有的能力：

按顺序遍历（中序遍历红黑树即升序）。
范围查询：subMap(from, to)、headMap、tailMap。
边界查询：firstKey、lastKey、ceilingKey（≥ 给定值的最小 key）、floorKey。

代价是查找 O(log n) 而非哈希表的 O(1)。所以要有序用 TreeMap，只按 key 快速存取用 HashMap。

三、HashMap 为什么引入红黑树（重点）

JDK 8 给 HashMap 加了「链表转红黑树」的优化，动机是防止哈希冲突导致的性能退化和攻击：

HashMap 用拉链法处理冲突，同一个桶里的元素挂成链表。正常情况链表很短，查找近似 O(1)。
但如果大量 key 哈希到同一个桶（哈希函数差，或恶意构造的碰撞攻击），链表会变得很长，查找退化到 O(n)。
JDK 8 的对策：当桶内链表长度 ≥ 8 且数组容量 ≥ 64 时，把该桶的链表转成红黑树，查找从 O(n) 降到 O(log n)。当树节点数减少到 ≤ 6 时再退化回链表。

为什么阈值是 8：在哈希均匀的理想情况下，一个桶里节点数服从泊松分布，长度达到 8 的概率极低（约千万分之六）。所以转树是「异常情况的兜底」，正常几乎不会触发；用 6/8 两个阈值（而非都用 8）是为了避免在临界点反复转换（抖动）。

四、为什么操作系统爱用红黑树

内核里很多场景要「维护一个动态有序集合，频繁插入删除、还要快速查找/取极值」：

CFS 调度：所有可运行进程按 vruntime（已运行的虚拟时间）排序，调度器每次要取「vruntime 最小」的进程运行。红黑树能 O(log n) 插入/删除进程、O(log n)（实际缓存最左节点后 O(1)）取最小，完美契合。
epoll、VMA、定时器：都是「大量条目 + 频繁增删 + 按某个键查找」的模式，红黑树的稳定 O(log n) 和低维护成本正合适。

五、什么时候不用红黑树

只需要按 key 快速存取、不要有序 → 用哈希表（HashMap），平均 O(1) 更快。
面向磁盘的大规模索引（数据库）→ 用 B/B+ 树，它是多路平衡树，一个节点存多个键、匹配磁盘页、减少 IO 次数，比红黑树更适合外存（属于 B树板块）。
查多写极少、追求极致查找 → AVL 也可考虑。

六、常见误区与追问

考点	正确口径
TreeMap/TreeSet	维护有序键和范围操作
HashMap 树化桶	冲突链过长时把最坏查找降为 O(log n)
内核定时器/调度	需要有序并频繁更新

HashMap bucket:
chain length >= threshold -> red-black tree
worst lookup: O(n) -> O(log n)

红黑树常出现在“既要有序，又要频繁插入删除”的工程位置。

误区：HashMap 使用红黑树是为了平均 O(1)。 平均 O(1) 来自哈希；红黑树是为了哈希冲突严重时改善桶内最坏复杂度。
误区：所有桶都会树化。 只有冲突链足够长且数组容量达到条件时才会树化，否则优先扩容。
误区：红黑树只适合内存数据结构。 内核和语言库中大量有序集合、定时器、调度结构都可使用红黑树。
追问：为什么不用 AVL 做 HashMap 树化桶？ 红黑树更新旋转较少，工程实现对插入删除更友好。
追问：TreeMap 需要红黑树解决什么？ 它要按 key 有序迭代、范围查找、前驱后继，同时保持 O(log n) 更新。
追问：什么时候不用红黑树？ 只做等值查找可用哈希表；磁盘索引更适合 B+ 树；前缀检索适合 Trie。

七、加强记忆

红黑树用于「有序 + 频繁增删 + 稳定 O(log n)」的场景：Java TreeMap/TreeSet、HashMap（链表 ≥8 且容量 ≥64 转红黑树、≤6 退回，把冲突严重时的桶查找从 O(n) 降到 O(log n)、防碰撞攻击）、C++ STL map/set、Linux CFS 调度/内存管理/epoll、Nginx 定时器。要有序用红黑树、只快速存取用哈希表、磁盘索引用 B+ 树。

简化版

详细版