为什么 HashMap 在 Java 8 之后选择使用红黑树，而不是普通的平衡二叉树？
在 Java 8 之前，HashMap 采用 数组 + 链表 解决哈希冲突，查询时间复杂度最坏情况下可达 O(n)。Java 8 引入 红黑树（Red-Black Tree） 作为优化方案，使得查询时间复杂度降低至 O(log n)。
那么，为什么 HashMap 选择 红黑树 而不是 AVL 树（严格平衡二叉搜索树） 这样的普通平衡二叉树呢？本文从 平衡性、性能、插入删除复杂度 角度进行解析。
1. 红黑树 vs. 普通平衡二叉树
特性
红黑树（Red-Black Tree）
AVL 树（严格平衡二叉搜索树）
平衡性
近似平衡（允许局部不平衡）
严格平衡（每个节点的左右子树高度差 ≤ 1）
查找时间复杂度
O(log n)（比链表快）
O(log n)（比红黑树更平衡）
插入删除复杂度
O(log n)（少量旋转）
O(log n)（旋转次数更多）
旋转操作
最多 2 次旋转（调整成本低）
最多 log(n) 次旋转（调整成本高）
性能
插入/删除操作更快
查找稍快，但插入删除开销大
结论：
AVL 树查找比红黑树更快（更严格平衡），但插入/删除代价更高。
红黑树允许适度不平衡，减少插入/删除时的旋转成本，性能更优。
2. HashMap 选择红黑树的核心原因
（1）插入和删除性能更优
在 HashMap 中，当 链表长度 ≥ 8 时，转换为红黑树，提高查找效率。
如果使用 AVL 树
AVL 树是严格平衡的，每次插入/删除都需要调整，使左右子树高度相等。
可能需要 多次旋转（最坏 log(n) 次），导致 插入/删除成本较高。
如果使用红黑树
允许局部不平衡，每次插入/删除只需 最多 2 次旋转（而不是 log(n) 次）。
插入和删除更快，适合 HashMap 的高并发环境。
✅ 结论：HashMap 需要高效的插入和删除，因此红黑树更优。
（2）查询速度的折中
AVL 树比红黑树查找更快（树更平衡，查询路径更短）。
但在 HashMap 中，树的高度最多是 log(8) = 3（最多 8 个节点）。
由于树的规模很小，AVL 树的查找优势并不明显。
但如果使用 AVL 树，插入/删除成本会变高。
✅ 结论：HashMap 中红黑树的 O(log 8) ≈ O(3) ≈ O(1) 查找速度已经足够快，没必要用 AVL 树提高查询速度，而应该优化插入/删除。
（3）减少 CPU 计算开销
AVL 树 为了保证平衡，需要在每次插入/删除后执行 严格的平衡检测。
红黑树 允许局部不平衡，减少了 不必要的旋转操作，减少 CPU 计算量，提高整体性能。
✅ 结论：红黑树比 AVL 树 计算成本更低，插入/删除操作更快。
3. HashMap 中的红黑树转换规则
Java 8 HashMap 规定：
当桶中的链表 长度 ≥ 8，转换为 红黑树（提高查找速度）。
当桶中的元素 减少到 ≤ 6，转换回 链表（减少额外的内存开销）。
这两个阈值的设计是经验优化，避免频繁转换导致的性能损耗。
4. 总结
✅ HashMap 选择红黑树的原因
插入/删除性能更优：红黑树 最多 2 次旋转，而 AVL 树需要 log(n) 次旋转，插入/删除更快。
查询速度折中：HashMap 的红黑树高度 最多 log(8) ≈ 3，查询速度已经接近 O(1)，无需 AVL 树的极致平衡。
减少 CPU 计算成本：红黑树的平衡调整更少，减少额外计算，提高整体性能。
适合 HashMap 的动态存储：当链表 ≥ 8 时转换为树，≤ 6 时恢复为链表，节省内存。
❌ 为什么不用 AVL 树？
AVL 树插入/删除旋转次数多，调整成本太高。
HashMap 中的树 不会太深，AVL 树的查询优化 意义不大。
5. 代码示例
import java.util.HashMap;
import java.util.Map;
public class HashMapTreeExample {
public static void main(String[] args) {
// 创建 HashMap
Map
// 插入 8 个哈希冲突的 Key，触发红黑树转换
for (int i = 0; i < 8; i++) {
map.put(i * 16, "Value" + i); // 产生相同 hash 桶
}
System.out.println("HashMap size: " + map.size());
}
}
✅ 当同一哈希桶中元素 ≥ 8，转换为红黑树，提高查询效率。
6. 结论
HashMap 选择红黑树而不是 AVL 树，主要是因为：
插入/删除更快（红黑树的旋转次数更少）。
查询速度已经足够快（最多 log(8) = 3 层）。
计算开销更低（红黑树的平衡调整更少）。
节省内存（数据少时转换回链表）。
🚀 因此，Java 8 HashMap 选择红黑树，避免了 AVL 树的高维护成本，提高了性能！