Java HashMap 从链表到红黑树的进化之路

在 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;
    }
    
}