我的生态
🧭
Java 面试指南覆盖面试高频考点，助你从容应对技术面试

    HashMap 红黑树化阈值

    面试官问："HashMap 什么时候会把链表转成红黑树？"

    候选人小何答："链表长度达到 8 的时候。"

    面试官点点头，继续问："那红黑树什么时候会退链表？"

    小何说："呃... 长度变成 6？"

    面试官追问："为什么是 8 和 6？不是对称的 8 和 8？"

    小何彻底答不上来。

    【面试官心理】 这道题考查的是候选人对 HashMap 源码的理解深度。能说出阈值的占 60%，能说出为什么非对称的占 20%，能解释泊松分布的只有 5%。这道题是 P6 和 P5 的分水岭。

    一、红黑树化阈值 🔴

    1.1 JDK 8 源码定义

    static final int TREEIFY_THRESHOLD = 8;   // 链表 → 红黑树
static final int UNTREEIFY_THRESHOLD = 6; // 红黑树 → 链表

static final int MIN_TREEIFY_CAPACITY = 64; // 树化的最小容量要求

    1.2 树化条件

    链表转红黑树需要同时满足两个条件：

    1. 链表长度 >= TREEIFY_THRESHOLD（8）
    2. HashMap 容量 >= MIN_TREEIFY_CAPACITY（64）
    final void treeifyBin(Node<K, V>[] tab, int hash) {
    int n, bin;

    // 如果容量小于 64，先扩容而不是树化
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else if ((bin = tabAt(tab, hash & (n - 1)) != null) {
        // 否则才树化
    }
}

    为什么容量小于 64 先扩容？

    因为这个时候数据量还不大，扩容可以解决哈希碰撞问题，没必要树化。

    二、为什么是 8？🔴

    2.1 泊松分布

    JDK 源码注释解释了为什么选择 8：

    // 理想情况下，随机哈希码下，链表节点的分布在泊松概率下：
// 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.00001579
// k=7 概率: 0.00000113
// k=8 概率: 0.00000006  ← 几乎不可能达到

// 所以阈值 8 是一个非常保守的选择

    2.2 链表 vs 红黑树的性能拐点

    数据结构查找插入删除
    链表O(n)O(1)*O(1)*
    红黑树O(log n)O(log n)O(log n)

    *插入/删除的 O(1) 前提是已知位置，查找位置仍需要 O(n)。

    链表和红黑树的性能拐点：

    • 链表长度 < 8：链表查找最多 7 次，红黑树 O(log n) = 3 次，链表更快
    • 链表长度 = 8：链表查找 8 次，红黑树仍只需 3 次，红黑树开始更快
    • 链表长度 > 8：红黑树优势明显

    三、为什么退链表阈值是 6 而不是 8？🔴

    3.1 避免在阈值边界反复树化/退链表

    如果退链表阈值也是 8：

    // 假设阈值为 8/8 对称
链表长度 8 → 树化
链表长度 7 → 退链表
链表长度 8 → 再次树化
// 不断在边界震荡！

    3.2 实际设计

    树化阈值: 8（链表长度 >= 8 时树化）
退链表阈值: 6（红黑树节点 <= 6 时退链表）

    这样设计形成了一个缓冲区：

    [0-6]: 纯链表（无树化）
[7]:   临界状态（不树化也不退链表）
[8+]:  树化状态

退链表时：
[8+] → 树化
[6-]:  退链表

    3.3 代码验证

    // JDK 8 HashMap
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;

// putVal 中的树化判断
if (binCount >= TREEIFY_THRESHOLD - 1)  // -1 是因为从 0 开始计数
    treeifyBin(tab, hash);

// 红黑树的退链表判断在 removeTreeNode 方法中
// 当树节点数 <= UNTREEIFY_THRESHOLD 时调用 untreeify

    四、为什么选择红黑树而不是 AVL？🟡

    4.1 AVL vs 红黑树

    特性AVL红黑树
    平衡性严格平衡近似平衡
    高度差<= 1最大 2 倍
    查找性能更好稍差
    插入/删除代价高（更多旋转）低（更少旋转）
    适用场景读多写少写多读少

    4.2 HashMap 的场景选择

    HashMap 是写多读少的数据结构：

    • 每次 put 都要找位置插入
    • get 操作虽然频繁，但 O(log n) 已经足够快
    • 插入性能比查找性能更重要

    因此选择插入代价更小的红黑树而不是 AVL。

    五、面试官追问 🔴

    面试官："如果 HashMap 容量小于 64 但链表很长，会怎么办？"

    标准回答：

    • 会先触发扩容而不是树化
    • 扩容后，链表会重新散列，可能变短
    • 只有容量 >= 64 且链表长度 >= 8 才会树化

    面试官追问："JDK 7 和 JDK 8 的 HashMap 有什么区别？"

    标准回答：

    • JDK 7：数组 + 链表，扩容时可能死循环
    • JDK 8：数组 + 链表 + 红黑树，避免了扩容死循环
    • JDK 8 还改变了扩容时的 transfer 顺序（非递归、头插改尾插）

    面试官追问："红黑树的查找一定比链表快吗？"

    标准回答：

    • 不一定。数据量小时，链表（O(n)）的常数项更小
    • 红黑树（O(log n)）的优势在数据量大时才明显
    • 所以阈值 8 是一个平衡点，不是随便选的

    六、生产避坑 🟡

    6.1 HashMap 死循环问题（JDK 7）

    // JDK 7 扩容时的 transfer（已废弃）
void transfer(Entry[] newTable) {
    Entry[] src = table;
    int newCapacity = newTable.length;
    for (int j = 0; j < src.length; j++) {
        Entry<K,V> e = src[j];
        if (e != null) {
            src[j] = null;
            do {
                Entry<K,V> next = e.next;
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];  // 头插法
                newTable[i] = e;
                e = next;
            } while (e != null);
        }
    }
}

    问题：多线程并发扩容时，链表节点顺序会反转，形成环形链表，导致 get() 死循环。

    解决：JDK 8 通过改变扩容顺序（非递归、尾插）解决了这个问题。

    6.2 不当的容量预设

    // ❌ 错误：预估 100 万数据，用默认容量 16
Map<String, Order> orders = new HashMap<>();  // 扩容 18+ 次

// ✅ 正确：预设容量，减少扩容
Map<String, Order> orders = new HashMap<>(1_000_000 / 0.75 + 1);

    七、总结

    阈值值含义
    TREEIFY_THRESHOLD8链表长度达到 8 时树化
    UNTREEIFY_THRESHOLD6红黑树节点减少到 6 时退链表
    MIN_TREEIFY_CAPACITY64树化的最小容量要求

    设计思想：

    • 8 是一个保守的阈值（泊松分布概率极低）
    • 6 而不是 8 是为了避免边界震荡
    • 红黑树而非 AVL 是因为 HashMap 写多读少