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

一、 核心源碼常量定義

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

/**
 * 1. 樹化閾值：當桶中鏈表長度大于該值時，嘗試轉為紅黑樹
 */
static final int TREEIFY_THRESHOLD = 8;
/**
 * 2. 退化閾值：當擴容或刪除節(jié)點導致樹節(jié)點數小于該值時，轉回鏈表
 */
static final int UNTREEIFY_THRESHOLD = 6;
/**
 * 3. 最小樹化容量：只有當數組總容量大于該值時，才會真正進行樹化
 */
static final int MIN_TREEIFY_CAPACITY = 64;

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

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

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

當我們在 put 一個元素時，如果發(fā)生碰撞且當前是鏈表結構，會進入以下邏輯：

// JDK 1.8 putVal 部分源碼
for (int binCount = 0; ; ++binCount) {
    if ((e = p.next) == null) {
        p.next = newNode(hash, key, value, null); // 插入新節(jié)點（尾插法）
        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，則優(yōu)先選擇擴容而不是樹化
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize(); 
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        // 只有數組長度 ≥ 64 且鏈表長度 > 8，才會執(zhí)行真正的樹化邏輯
        // ... 將 Node 轉換為 TreeNode 的過程
    }
}

三、 深度思考：背后的數學與工程考量

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

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

設計用意：正常情況下，我們幾乎不會遇到樹化。紅黑樹是為了應對那些哈希函數設計不佳，甚至遭受惡意哈希攻擊導致大量碰撞的情況。

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

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

3. 節(jié)點結構的巨大變化

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

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

空間代價：TreeNode 占用的內存空間大約是普通 Node 的 2 倍。

四、 總結：HashMap 的進化準則

鏈表轉紅黑樹：當前桶鏈表長度

 且數組總容量 。

紅黑樹轉鏈表：在擴容或刪除元素時，若樹中節(jié)點數 。

• 核心哲學：
  • 容量小、碰撞多：通過 resize 擴容來平攤碰撞。
  • 容量大、碰撞多：通過 treeify 提升查詢效率（從 O(n) 降至 O(log n)）。

?? 面試貼士

在面試中，如果面試官問：“HashMap 什么時候樹化？”，完整的回答應該是：

“當鏈表長度超過 8 時，HashMap 會調用 treeifyBin 方法。但該方法內部會先判斷數組容量，如果容量小于 64，會優(yōu)先擴容；只有容量大于等于 64 且鏈表長度達到 8，才會正式轉換為紅黑樹。”

到此這篇關于深入淺出 Java HashMap：從鏈表到紅黑樹的“進化”之路的文章就介紹到這了,更多相關Java HashMap鏈表到紅黑樹內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！