【Java集合】深入浅出 Java HashMap：从链表到红黑树的“进化”之路

🍂 枫言枫语：我是予枫，一名行走在 Java 后端与多模态 AI 交叉路口的研二学生。 “予一人以深耕，观万木之成枫。” 在这里，我记录从底层源码到算法前沿的每一次思考。希望能与你一起，在逻辑的丛林中寻找技术的微光。

在 Java 集合框架中，HashMap 的底层实现在 JDK 1.8 迎来了一次重大革新：引入了红黑树。这一设计并非为了酷炫，而是为了解决哈希碰撞导致的性能退化问题。本文将结合底层源码，带你彻底搞懂 HashMap 是在什么条件下、如何进行树化的。

一、 核心源码常量定义

在 HashMap.java 中，有三个关键常量决定了树化与退化的阈值：

/**
 * 1. 树化阈值：当桶中链表长度大于该值时，尝试转为红黑树
 */
static final int TREEIFY_THRESHOLD = 8;

/**
 * 2. 退化阈值：当扩容或删除节点导致树节点数小于该值时，转回链表
 */
static final int UNTREEIFY_THRESHOLD = 6;

/**
 * 3. 最小树化容量：只有当数组总容量大于该值时，才会真正进行树化
 */
static final int MIN_TREEIFY_CAPACITY = 64;

二、 树化的“双重条件”深度逻辑

很多开发者只记得“链表长度 > 8”，但实际上源码中存在一个隐藏的判定逻辑。

1. 触发入口：putVal 方法

当我们在 put 一个元素时，如果发生碰撞且当前是链表结构，会进入以下逻辑：

// JDK 1.8 putVal 部分源码
for (int binCount = 0; ; ++binCount) {
    if ((e = p.next) == null) {
        p.next = newNode(hash, key, value, null); // 插入新节点（尾插法）
        if (binCount >= TREEIFY_THRESHOLD - 1) // 如果链表长度达到 8
            treeifyBin(tab, hash); // 尝试树化
        break;
    }
    // ... 忽略省略部分
}

2. 核心判定：treeifyBin 方法

进入 treeifyBin 后，并不是直接转红黑树，它会先检查数组的长度：

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    // 【核心判定】
    // 如果数组为空，或者数组长度 n < 64，则优先选择扩容而不是树化
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize(); 
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        // 只有数组长度 ≥ 64 且链表长度 > 8，才会执行真正的树化逻辑
        // ... 将 Node 转换为 TreeNode 的过程
    }
}

三、 深度思考：背后的数学与工程考量

1. 为什么是 8？—— 泊松分布

根据 HashMap 源码注释，节点在哈希桶中的频率遵循泊松分布。在负载因子为 0.75 的情况下，链表长度达到 8 的概率极低，约为 0.00000006。

设计用意：正常情况下，我们几乎不会遇到树化。红黑树是为了应对那些哈希函数设计不佳，甚至遭受恶意哈希攻击导致大量碰撞的情况。

2. 为什么退化阈值是 6 而不是 7？

这是为了留出缓冲区。如果退化阈值也是 8，那么当一个桶的节点数在 7 和 8 之间反复变动时，会引起频繁的“树化 <-> 退化”转换。这会导致大量的 TreeNode 与 Node 对象的创建与销毁，严重影响性能。

3. 节点结构的巨大变化

树化不仅仅是逻辑变了，底层存储的对象类型也发生了质变：

• 链表节点 (Node)：包含 hash, key, value, next。
• 树节点 (TreeNode)：继承自 LinkedHashMap.Entry，除了基本属性，还增加了 parent, left, right, prev, red（红黑属性）。

空间代价：TreeNode 占用的内存空间大约是普通 Node 的 2 倍。

四、 总结：HashMap 的进化准则

1. 链表转红黑树：当前桶链表长度

$\ge 8$

且数组总容量

$\ge 64$

。

1. 红黑树转链表：在扩容或删除元素时，若树中节点数

$\le 6$

。

1. 核心哲学：
   • 容量小、碰撞多：通过 resize 扩容来平摊碰撞。
   • 容量大、碰撞多：通过 treeify 提升查询效率（从 O(n) 降至 O(log n)）。

💡 面试贴士

在面试中，如果面试官问：“HashMap 什么时候树化？”，完整的回答应该是：

“当链表长度超过 8 时，HashMap 会调用 treeifyBin 方法。但该方法内部会先判断数组容量，如果容量小于 64，会优先扩容；只有容量大于等于 64 且链表长度达到 8，才会正式转换为红黑树。”

关于作者： 💡 予枫，某高校在读研究生，专注于 Java 后端开发与多模态情感计算。💬 欢迎点赞、收藏、评论，你的反馈是我持续输出的最大动力！

我的博客即将同步至腾讯云开发者社区，邀请大家一同入驻： https://cloud.tencent.com/developer/support-plan?invite_code=9wrxwtlju1l 当前加入还有惊喜相送！