为什么在 Jdk 8 中 HashMap 要转成红黑树？

结论先行：链表在哈希冲突严重时退化成 O(n)，攻击者可以构造大量同 hash 的 key，把 HashMap 变成一条长链，拖垮 CPU——这是实打实的拒绝服务风险。JDK 8 在桶内节点足够多时把链表转成红黑树，把单桶最坏查找从 O(n) 降到 O(log n)。触发条件不是“长度到 8 就转”，而是桶内已有 8 个节点、再插入第 9 个，并且表容量至少 64。

1. 链表与红黑树的差距

冲突严重时的链表桶（容量 64，9 个节点挤在同一个桶）
tab[i] → A → B → C → D → E → F → G → H → I
查找 I 需要比较 9 次，攻击者可以构造上万个同 hash 的 key

树化之后（红黑树，查找走二叉比较）
              D(黑)
            /      \
         B(红)     H(红)
        /   \     /   \
      A     C   F     I
               \
                G
查找 I：D → H → I，3 次比较

2. 三个阈值各管什么

8 与 6 之间留出缓冲，是为了避免节点数在边界来回抖动时反复“树化—退化”，白白消耗 CPU。

3. 源码入口

// putVal 中链表尾插之后
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
    treeifyBin(tab, hash);

// treeifyBin：容量不够就扩容，够大才真正建树
final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();                                  // 小表先扩容，摊开节点
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        // 把整条链替换成 TreeNode，再调用 treeify 建红黑树
    }
}

源码注释写得明确：“Bins are converted to trees when adding an element to a bin with at least this many nodes.” 计数从桶内第 2 个节点开始（binCount 从 0 起），所以 binCount >= 7 对应“桶内已有 8 个节点，正在插入第 9 个”。

4. 代码：制造碰撞观察树化

import java.util.HashMap;
import java.util.Map;

public class TreeifyDemo {
    // 所有实例 hashCode 相同，equals 按 id 区分
    static final class BadKey implements Comparable<BadKey> {
        final int id;
        BadKey(int id) { this.id = id; }
        @Override public int hashCode() { return 1; }
        @Override public boolean equals(Object o) {
            return o instanceof BadKey && ((BadKey) o).id == id;
        }
        @Override public int compareTo(BadKey o) { return Integer.compare(id, o.id); }
    }

    public static void main(String[] args) {
        // 容量必须 >= 64 才会树化，否则 treeifyBin 会先扩容
        Map<BadKey, Integer> map = new HashMap<>(64);
        for (int i = 0; i < 9; i++) {
            map.put(new BadKey(i), i); // 第 9 个节点写入时触发树化
        }
        System.out.println(map.get(new BadKey(8))); // 输出：8
    }
}

把 new HashMap<>(64) 换成默认构造，前几次 put 只会不断扩容，桶里的节点被摊到新数组，未必能观察到树化——这也是 MIN_TREEIFY_CAPACITY 存在的意义。

5. 树化付出的代价

• TreeNode 比普通 Node 多出 parent、left、right、prev 四个引用和颜色位，内存约翻倍。
• 插入和删除要做红黑树平衡，常数开销大于链表尾部追加。
• 桶内节点数很少时（1~3 个），树的优势根本体现不出来，反而更慢。
• 维护两套结构增加了实现复杂度，split、untreeify、removeTreeNode 都要处理链表与树的互转。

因此策略是“默认用链表，只有病态桶才升级成树”，而不是全表用树。

6. 退化规则

removeTreeNode 在树变得过小（根为空、左右子树不足）时直接把整棵树 untreeify 成链表；resize 的 split 里，拆分后节点数 ≤ 6 的一侧也退回链表。阈值不对称正是为了防抖动。

常见追问

• 为什么不直接用红黑树？ 正常哈希下桶里平均不到 1 个节点，树的内存和操作开销都是纯亏损。
• 为什么阈值是 8？ 官方注释的泊松分布给出：0.75 负载下桶内 8 个节点的概率约 6e-8，正常业务几乎不会触发。
• 为什么容量小于 64 不树化？ 小表出现长链多半是表太小，扩容把节点摊开的收益比建树更大。
• 树化时 key 怎么比较？ 先比 hash，再尝试 Comparable，最后用 System.identityHashCode 兜底（tieBreakOrder），保证有一个稳定的序。
• 红黑树能彻底防住哈希碰撞攻击吗？ 能缓解到 O(log n)，但如果 key 不可比较且大量同 hash，插入仍会走兜底比较，效果有限。
• 树化后迭代顺序变了吗？ 没变，TreeNode 同时维护 next 链，遍历仍按原链表顺序。

小结

JDK 8 引入红黑树，本质是给“哈希分布病态”这个最坏情况加一层保险：正常桶继续用链表，省内存；桶内节点超过 8 个且表容量足够时升级为红黑树，把最坏查找压到 O(log n)。记住三个数字——9（插入第 9 个才树化）、64（容量门槛）、6（退化阈值），以及一句原理：链表怕长，树怕多，所以只在长链上建树。