快捷導(dǎo)航

Java HashMap從鏈表到紅黑樹的"進(jìn)化"過程詳解

更新時間：2026年02月05日 11:30:15 作者：予楓的編程筆記

在Java集合框架中,HashMap的底層實(shí)現(xiàn)在JDK 1.8迎來了一次重大革新：引入了紅黑樹,本文將結(jié)合底層源碼,帶你徹底搞懂HashMap是在什么條件下、如何進(jìn)行樹化的,感興趣的朋友跟隨小編一起看看吧

在 Java 集合框架中，HashMap 的底層實(shí)現(xiàn)在 JDK 1.8 迎來了一次重大革新：引入了紅黑樹。這一設(shè)計(jì)并非為了酷炫，而是為了解決哈希碰撞導(dǎo)致的性能退化問題。本文將結(jié)合底層源碼，帶你徹底搞懂 HashMap 是在什么條件下、如何進(jìn)行樹化的。

一、核心源碼常量定義

在 HashMap.java 中，有三個關(guān)鍵常量決定了樹化與退化的閾值：

/**
 * 1. 樹化閾值：當(dāng)桶中鏈表長度大于該值時，嘗試轉(zhuǎn)為紅黑樹
 */
static final int TREEIFY_THRESHOLD = 8;
/**
 * 2. 退化閾值：當(dāng)擴(kuò)容或刪除節(jié)點(diǎn)導(dǎo)致樹節(jié)點(diǎn)數(shù)小于該值時，轉(zhuǎn)回鏈表
 */
static final int UNTREEIFY_THRESHOLD = 6;
/**
 * 3. 最小樹化容量：只有當(dāng)數(shù)組總?cè)萘看笥谠撝禃r，才會真正進(jìn)行樹化
 */
static final int MIN_TREEIFY_CAPACITY = 64;

二、樹化的“雙重條件”深度邏輯

很多開發(fā)者只記得“鏈表長度 > 8”，但實(shí)際上源碼中存在一個隱藏的判定邏輯。

1. 觸發(fā)入口：putVal方法

當(dāng)我們在 put 一個元素時，如果發(fā)生碰撞且當(dāng)前是鏈表結(jié)構(gòu)，會進(jìn)入以下邏輯：

// JDK 1.8 putVal 部分源碼
for (int binCount = 0; ; ++binCount) {
    if ((e = p.next) == null) {
        p.next = newNode(hash, key, value, null); // 插入新節(jié)點(diǎn)（尾插法）
        if (binCount >= TREEIFY_THRESHOLD - 1) // 如果鏈表長度達(dá)到 8
            treeifyBin(tab, hash); // 嘗試樹化
        break;
    }
    // ... 忽略省略部分
}

2. 核心判定：treeifyBin方法

進(jìn)入 treeifyBin 后，并不是直接轉(zhuǎn)紅黑樹，它會先檢查數(shù)組的長度：

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    // 【核心判定】
    // 如果數(shù)組為空，或者數(shù)組長度 n < 64，則優(yōu)先選擇擴(kuò)容而不是樹化
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize(); 
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        // 只有數(shù)組長度 ≥ 64 且鏈表長度 > 8，才會執(zhí)行真正的樹化邏輯
        // ... 將 Node 轉(zhuǎn)換為 TreeNode 的過程
    }
}

三、深度思考：背后的數(shù)學(xué)與工程考量

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

根據(jù) HashMap 源碼注釋，節(jié)點(diǎn)在哈希桶中的頻率遵循泊松分布。在負(fù)載因子為 0.75 的情況下，鏈表長度達(dá)到 8 的概率極低，約為 0.00000006。

設(shè)計(jì)用意：正常情況下，我們幾乎不會遇到樹化。紅黑樹是為了應(yīng)對那些哈希函數(shù)設(shè)計(jì)不佳，甚至遭受惡意哈希攻擊導(dǎo)致大量碰撞的情況。

2. 為什么退化閾值是 6 而不是 7？

這是為了留出緩沖區(qū)。如果退化閾值也是 8，那么當(dāng)一個桶的節(jié)點(diǎn)數(shù)在 7 和 8 之間反復(fù)變動時，會引起頻繁的“樹化 <-> 退化”轉(zhuǎn)換。這會導(dǎo)致大量的 TreeNode 與 Node 對象的創(chuàng)建與銷毀，嚴(yán)重影響性能。

3. 節(jié)點(diǎn)結(jié)構(gòu)的巨大變化

樹化不僅僅是邏輯變了，底層存儲的對象類型也發(fā)生了質(zhì)變：

鏈表節(jié)點(diǎn) (Node)：包含 hash, key, value, next。
樹節(jié)點(diǎn) (TreeNode)：繼承自 LinkedHashMap.Entry，除了基本屬性，還增加了 parent, left, right, prev, red（紅黑屬性）。