HashMap底层-红黑树#

一句话答案#

红黑树是近似平衡 BST，五大性质保证最长路径不超最短两倍，HashMap 链表 ≥8 时转红黑树提升查找到 O(logn)。

核心要点

红黑树五性质： 1.非红即黑 2.根黑 3.叶(NIL)黑 4.红无红子 5.黑路同数

HashMap 中的使用： 链表≥8 且数组≥64 → 转红黑树；节点≤6 → 退化链表

AVL vs 红黑树： AVL 查找更快但插删旋转多；红黑树增删少旋转，适合 HashMap/TreeMap

平衡性推导：从五性质到 O(logn)#

目标： 证明含 n 个节点的红黑树高度 h ≤ 2log₂(n+1)，从而查找/插入/删除都是 O(logn)。

第 1 步｜定义黑高 bh： 从某节点出发到任一叶子（NIL）路径上的黑节点数。由性质 5「黑路同数」，bh 对该节点是唯一确定的，与走哪条路径无关。

第 2 步｜最长路径 ≤ 2×最短路径： 由性质 4「红不连红」，任一路径上红节点不能相邻，所以红节点数 ≤ 黑节点数。

• 最短路径：全黑，长度 = bh
• 最长路径：红黑交替，长度 ≤ 2·bh

这就是「最长不超最短两倍」的来源，也是「近似平衡」标签的精确含义。

第 3 步｜节点数下界推树高： 黑高为 bh 的子树至少包含一棵「去掉所有红节点后」的完美黑树，其内部节点数 ≥ 2^bh − 1，即

$n \ge 2^{bh}-1 \;\Rightarrow\; bh \le \log_2(n+1)$

由第 2 步整棵树高 h ≤ 2·bh，代入得

$h \le 2\log_2(n+1) = O(\log n)$

操作沿树高走一遍，故均为 O(logn)。

红黑树 ↔ 2-3-4 树本质#

红黑树是 2-3-4 树（4 阶 B 树）的二叉表示——这才是平衡性的真正根源，五条性质只是把这个等价关系翻译成二叉树上的约束。

对应规则： 红节点 = 与其父节点「同属一个 B 树节点」，黑节点才是 B 树节点的代表。

为什么必然平衡： B 树天生所有叶子在同一层（完美平衡）。把每个 B 树节点「展开」成黑节点带红节点的小簇后：

• 「所有叶子同层」⟹ 性质 5「黑路同数」（每个 B 层贡献恰好 1 个黑节点）
• 「红节点只是同簇内的伴随节点、不能再带红」⟹ 性质 4「红不连红」

一句话：红黑树的平衡不是靠五条性质「凑」出来的，而是它本质上就是一棵完美平衡的 2-3-4 树。

插入修复的核心 case#

新节点先涂红插入（不破坏黑高），只可能违反「红不连红」，看叔叔节点颜色分两类：

① 叔叔为红（变色 + 上溯）： 父、叔变黑，祖父变红，把「冲突」上移到祖父继续检查。对应 2-3-4 树里 4 节点「溢出分裂」、中键上提到上层——所以可能一路上溯到根（根再涂黑）。

② 叔叔为黑/NIL（旋转 + 变色，终止）： 先把「父-子-祖父」拐折情况（LR/RL）旋转成一条直线（LL/RR），再以祖父为中心单旋 + 父祖变色。旋转后局部恢复，无需继续上溯。

记忆：叔红就变色上溯，叔黑就旋转收尾。插入最多 2 次旋转，删除最多 3 次旋转。

面试回答（2分钟版）

红黑树是一种近似平衡的二叉搜索树，通过五条性质保证平衡：节点非红即黑、根节点为黑、叶子NIL节点为黑、红节点的子节点必须为黑即不能红红相连、从任一节点到其所有叶子的路径上黑色节点数相同。这五条性质保证了最长路径不超过最短路径的两倍，从而查找时间维持在O(logn)。HashMap在JDK8引入红黑树做优化，当链表长度大于等于8且数组容量大于等于64时转为红黑树，当节点数降到6以下退化回链表。为什么不一开始就用红黑树？因为节点少时链表遍历开销比红黑树的维护开销更小，红黑树每个节点还要额外存储颜色、父指针、左右子指针占内存更多。对比AVL树，AVL是严格平衡左右子树高度差不超过1，查找更快但插入删除时旋转操作更频繁。红黑树插入最多两次旋转删除最多三次旋转，增删性能更优，所以HashMap和TreeMap都选用红黑树。

追问与易错

追问方向：

• “红黑树和 AVL 树怎么选？”→ AVL 严格平衡（左右子树高差≤1），查询更快但插入删除旋转多；红黑树近似平衡，增删性能更好；读多用 AVL，写多用红黑树，Java 集合统一用红黑树
• “HashMap 为什么不一直用红黑树？”→ 链表在元素少时（<8）遍历开销很小且无需维护平衡的额外开销；红黑树节点占用空间是链表节点的两倍，元素少时性价比低
• “红黑树的旋转操作理解吗？”→ 左旋/右旋是局部操作，O(1) 时间调整指针关系；插入最多 2 次旋转 + 变色，删除最多 3 次旋转 + 变色，保证黑高一致和无连续红节点
• “怎么从五性质推出 O(logn)？”→ 黑路同数定义出黑高 bh；红不连红 ⟹ 红节点 ≤ 黑节点 ⟹ 最长路径 ≤ 2·bh；黑高 bh 的子树至少 2^bh−1 个节点 ⟹ bh ≤ log(n+1) ⟹ 树高 ≤ 2log(n+1) = O(logn)
• “红黑树和 2-3-4 树什么关系？”→ 红黑树就是 4 阶 B 树（2-3-4 树）的二叉表示，红节点表示「与父同属一个 B 树节点」（3 节点=1 红 1 黑，4 节点=2 红 1 黑）；B 树所有叶子同层 ⟹ 黑路同数，B 树节点内不能再嵌 ⟹ 红不连红，平衡性由此而来

易错点：

• ❌ 红黑树就是平衡二叉树——是近似平衡
• ❌ HashMap 链表到 8 就转——还需数组长度 >=64