HashMap 链表长度为什么到 8 才转红黑树？为什么用红黑树而不是 AVL 树？

简化版

链表到 8 才树化，是因为在负载因子 0.75 的泊松分布下，一个桶堆到 8 个元素的概率低到千万分之六，几乎不可能自然发生——设成 8 是「链表已经异常长、值得升级」的兜底线，同时避免频繁树化。用红黑树而不是 AVL，是因为 HashMap 里增删（put/扩容迁移）很频繁：红黑树是「弱平衡」，插入删除最多旋转 2~3 次；AVL 是「严格平衡」，插入删除可能一路旋转到根，维护成本更高。红黑树牺牲一点查询高度，换来更低的增删开销，更适合读写都多的场景。

详细版

为什么树化阈值是 8：

树化的目的是给「极端哈希冲突」兜底：正常情况链表极短（0~1 个元素），根本用不上树；
泊松分布下，负载因子 0.75 时单桶元素数达到 8 的概率约为 6e-8，属于「几乎不会自然发生」的事件——设成 8，就是让树化成为罕见的保底机制，而不是常态；
阈值太小会导致频繁树化，而 TreeNode 内存是普通 Node 的约 2 倍、树化本身也有开销，得不偿失。

还有个隐藏条件：链表长度到 8 时，还要数组长度 ≥64 才真正树化；否则优先扩容（扩容能把冲突元素分散到更多桶）。

为什么退化阈值是 6：删除/扩容让树节点降到 6 才退化回链表。8 和 6 之间留缓冲，避免元素在 7、8 附近反复增删导致「树化↔退化」抖动。

为什么用红黑树而不是 AVL：

维度	红黑树	AVL 树
平衡程度	弱平衡（最长路径 ≤ 2× 最短）	严格平衡（左右子树高度差 ≤1）
查询	O(log n)，略慢	O(log n)，更快（更矮）
插入旋转	最多 2 次	可能 O(log n) 次
删除旋转	最多 3 次	可能 O(log n) 次
适合场景	增删频繁	查询远多于增删

HashMap 的桶会频繁 put、扩容时整棵树要拆分重建，增删密集，红黑树的低维护成本更划算。

// 极端情况：故意让大量 key 哈希碰撞，桶内链表被树化
Map<Key, Integer> map = new HashMap<>();
// 若 Key.hashCode() 恒返回同一值，元素全挤一个桶 → 达到阈值后转红黑树

⚠️ 树化不是「链表长就一定发生」，前置条件是数组长度 ≥64；小表优先扩容而非树化。

完整版教学

一、树化是「兜底」，不是「常态」

先纠正一个直觉误区：红黑树在 HashMap 里不是主角，是备胎。正常使用时哈希分布均匀，每个桶里就 0~1 个元素，链表短到可以忽略，get/put 都是 O(1)，红黑树根本不出场。

红黑树只为一种情况准备：哈希严重冲突——可能是你的 hashCode 写得烂（大量 key 撞一个桶），也可能是攻击者故意构造相同 hashCode 的 key 做 DoS（让某个桶退化成长链表，查询 O(n)，拖垮服务）。这时把链表转成红黑树，查询从 O(n) 拉回 O(log n)，是一道安全兜底。理解了「兜底」定位，才能理解为什么阈值定得那么高。

二、阈值 8 的来历：泊松分布算给你看

JDK 源码里有段注释，直接给出了负载因子 0.75、随机哈希下，单个桶里元素数 k 的概率（泊松分布 λ≈0.5）：

k = 0:  0.60653066
k = 1:  0.30326533
k = 2:  0.07581633
k = 3:  0.01263606
k = 4:  0.00157952
k = 5:  0.00015795
k = 6:  0.00001316
k = 7:  0.00000094
k = 8:  0.00000006   ← 约 6 千万分之 1

看这串数字：一个桶里堆到 8 个元素的概率只有 6e-8，几乎不可能自然出现。所以阈值定 8 的逻辑是——只要真的堆到 8，就说明哈希分布已经异常（不是烂 hashCode 就是被攻击），这时树化的收益远大于成本。若把阈值定成 2、3，正常数据也会频繁触发树化，白白付出 TreeNode 的内存和转换开销。

三、为什么退化是 6，不是 7：留缓冲避免抖动

树化阈值 8、退化阈值 6，中间空了个 7。这是刻意的「滞回设计」。假设树化和退化都用同一个阈值 8，那么当一个桶恰好在 8 附近反复「加一个→删一个→加一个」，就会不停「树化→退化→树化」，每次转换都有开销，形成抖动。

若阈值都是 8：  ...7 →(加)8 树化 →(删)7 退化 →(加)8 树化...  反复抖动
实际设计：      树化=8，退化=6，中间 7 是缓冲带
               8 树化后，要删到 ≤6 才退化，不会一加一删就来回转

这跟恒温器「到 26℃ 才制冷、降到 24℃ 才停」是同一个道理——用一个死区（deadband）消除临界抖动。

四、还有个前置条件：数组长度 ≥64

很多人只记「链表到 8 树化」，漏了另一半：treeifyBin 里会先判断数组长度，如果 table.length < 64，不树化，而是先扩容 resize()。

道理很简单：小数组桶少，冲突本来就容易，某个桶到 8 很可能是「桶太少」而非「哈希真坏」。这时扩容（桶翻倍）能把挤在一起的元素重新分散开，比树化更划算——扩容后链表自然变短，没必要动用重量级的红黑树。只有数组已经够大（≥64）、扩容也解决不了，才说明是真冲突，才树化。

链表长度到 8：
  ├─ table.length < 64  → 扩容（分散冲突），不树化
  └─ table.length ≥ 64  → 真·树化

五、红黑树 vs AVL：为什么选「弱平衡」

两种都是自平衡二叉搜索树，查询都是 O(log n)，区别在平衡的严格程度，进而决定了增删的旋转成本：

AVL 树：严格平衡，任意节点左右子树高度差 ≤1。树更矮，查询略快；但代价是插入/删除后为维持严格平衡，可能从插入点一路旋转到根，最坏 O(log n) 次旋转。
红黑树：弱平衡，只保证「最长路径 ≤ 2× 最短路径」。树可能略高一点，查询略慢；但插入最多 2 次旋转、删除最多 3 次旋转就能恢复平衡，增删维护便宜得多。

HashMap 的桶是「读写都频繁」的场景：put 会插入，扩容时整棵树要按高低位拆成两棵，删除也常发生。增删密集的场景，红黑树用「查询慢一丁点」换「增删省很多旋转」，总账更划算。如果是「建好几乎只查」的场景，AVL 才更合适。

六、TreeNode 的代价：为什么不无脑树化

既然红黑树查询是 O(log n)，为什么不一开始就用树？因为红黑树的每个节点更重：

对比项	普通链表 Node	红黑树 TreeNode
额外字段	next	parent、left、right、prev、red 标志
单节点内存	约 32 字节	约 64 字节（≈2 倍）
短数据（<8）性能	遍历极快	反而更慢（要维护树结构）

桶里只有 1~2 个元素时，链表遍历一两步就完事，比走树结构还快，且省一半内存。所以 HashMap 的策略是「小数据用链表、大数据才升级树」，用最小成本覆盖大多数情况，只在极端时才付出树的代价。

记忆钩子：「8 树化、6 退化、64 才准树、红黑因为增删多」——四个数字/结论串起整道题。

七、常见误区与追问

误区：链表长度一到 8 就树化。 还要数组长度 ≥64；小表优先扩容分散冲突，不树化。
误区：树化后就永远是树。 删除或扩容让节点数降到 6 会退化回链表，省内存。
误区：红黑树比 AVL 查询快。 恰恰相反，AVL 更严格平衡、树更矮、查询略快；红黑树胜在增删维护便宜。
误区：TreeNode 和 Node 一样大。 TreeNode 多了 parent/left/right/prev 等字段，约为普通 Node 的 2 倍，所以短链表不划算。
追问：为什么退化阈值 6 而不是 8？ 8 和 6 之间留缓冲带（滞回），避免元素在阈值附近反复增删导致树化/退化频繁抖动。
追问：树化的时间复杂度是多少？ 树化要遍历链表并逐个插入红黑树，O(n log n) 级（n 是链长）；但因触发概率极低，摊到整体几乎无影响。
追问：为什么不用跳表？ 跳表也能 O(log n)，但空间开销（多层指针）大、实现更复杂；红黑树在单桶小规模数据下更省内存、更契合已有 Node 结构。

八、加强记忆

把树化理解成 HashMap 的「安全气囊」：平时（链表 01 个元素）根本不弹出，只有撞车级别的哈希冲突才启用。阈值 8 来自泊松分布——0.75 负载下堆到 8 的概率只有千万分之六，堆到 8 就意味着哈希已经异常，值得升级；但还有前置条件 数组 ≥64，否则先扩容分散冲突（小表冲突多半是桶太少）；退化用 6 而非 8，留出滞回缓冲带避免抖动。选红黑树而非 AVL，是因为桶里 put、扩容拆分、删除都频繁，红黑树「弱平衡」让增删最多旋转 23 次，用一点查询高度换大量增删成本，比严格平衡的 AVL 更适合读写都多的哈希桶；而不无脑树化，是因为 TreeNode 内存翻倍、短数据链表反而更快。记住「8 树化、6 退化、64 才准树、红黑为增删」，这道深挖题就答满了。

简化版

详细版