再談 HashMap：JDK 7 vs JDK 8 核心演進、哈希碰撞紅黑樹化、擴容機制優化與 DoS 防禦實測

HashMap 核心數據結構演進

一、JDK 8 樹化機制：從 O(n) 到 O(log n) 的質變

觸發條件（雙重判斷）

// Node.java 核心邏輯片段
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;

void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) {
        resize(); // 數組太小，優先擴容而非樹化
        return;
    }
    // ... 將鏈表轉換為 TreeNode 紅黑樹
}

• 條件 1：鏈表長度 ≥ TREEIFY_THRESHOLD (8)。
• 條件 2：數組容量 ≥ MIN_TREEIFY_CAPACITY (64)。若容量不足，優先 resize() 擴容分散碰撞。
• 逆向樹化：擴容後桶元素 ≤ UNTREEIFY_THRESHOLD (6)，紅黑樹退化為鏈表。

紅黑樹節點：TreeNode<K,V> 繼承 Node<K,V>

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // 紅黑樹父節點
    TreeNode<K,V> left;    // 左子節點
    TreeNode<K,V> right;   // 右子節點
    TreeNode<K,V> prev;    // 鏈表前驅（用於遍歷/擴容遷移）
    boolean red;           // 紅黑樹顏色
    // treeify/split/rotate/balance 等紅黑樹操作...
}

二、擴容機制優化：高位判斷法

JDK 7：全量 rehash

// 必須重新計算每個 key 的 hash & (newCap - 1)
for (Entry<K,V> e : oldTable) {
    while (e != null) {
        Entry<K,V> next = e.next;
        int i = hash(e.key) & (newCap - 1); // 重新計算索引
        e.next = newTable[i];
        newTable[i] = e;
        e = next;
    }
}

JDK 8：高位比特決定留/遷

// 核心邏輯：e.hash & oldCap 判斷高位是否為 1
Node<K,V>[] newTab = new Node[newCap];
for (Node<K,V> e : oldTab) {
    if (e == null) continue;
    if (e.next == null) { // 單節點直接遷移
        newTab[e.hash & (newCap - 1)] = e;
    } else if (e instanceof TreeNode) { // 紅黑樹分裂
        ((TreeNode<K,V>)e).split(newTab, oldCap, newCap);
    } else { // 鏈表分裂：保持原序（尾插法優勢）
        Node<K,V> loHead = null, loTail = null;
        Node<K,V> hiHead = null, hiTail = null;
        Node<K,V> next;
        do {
            next = e.next;
            if ((e.hash & oldCap) == 0) { // 高位為 0，留在原索引
                if (loTail == null) loHead = e;
                else loTail.next = e;
                loTail = e;
            } else { // 高位為 1，遷移到原索引 + oldCap
                if (hiTail == null) hiHead = e;
                else hiTail.next = e;
                hiTail = e;
            }
            e = next;
        } while (e != null);
        if (loTail != null) { loTail.next = null; newTab[j] = loHead; }
        if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; }
    }
}

優勢：無需重新計算 hash，僅判斷高位比特，**效能大幅提升**，且鏈表順序不反轉（避免 JDK 7 並發擴容死循環）。

三、實測：正常分布 vs 極端碰撞（DoS 攻擊模擬）

測試環境

• Key 類：hashCode() 返回固定值（極端碰撞）或連續值（正常分布）。
• Map 大小：10 ~ 1,000,000 (10 的冪次)。
• 操作：map.get(key) 循環訪問。

正常分布：JDK 8 比 JDK 7 快 ~20%（單次 get < 10ns @ 100 萬數據）

得益於擴容優化、內存佈局緊湊、JIT 友好。

極端碰撞（hashCode() 恒返 0）：複雜度從 O(n) 降為 O(log n)

// 惡意 Key
class EvilKey implements Comparable<EvilKey> {
    private final int id;
    @Override public int hashCode() { return 0; } // 所有 Key 同一桶
    @Override public int compareTo(EvilKey o) { return Integer.compare(this.id, o.id); }
    // equals 正確實現...
}

結論：JDK 8 樹化機制將惡意碰撞 DoS 攻擊面從線性降為對數，**有效防禦 HashDoS**。

四、Comparable 輔助排序：樹化時的關鍵契約

• 當 hashCode() 相同且 equals() 不同時，紅黑樹需比較大小決定左右子樹。
• Key 實現 Comparable<K> 可獲得最佳樹化效能**
• 若 Key 不實現 Comparable，JDK 8 會嘗試用 Class.getName() 比較（不穩定），甚至退化為鏈表行為。

// 良好的 Key 實現
class GoodKey implements Comparable<GoodKey> {
    private final long id;
    @Override public int hashCode() { return Long.hashCode(id); }
    @Override public boolean equals(Object o) { ... }
    @Override public int compareTo(GoodKey o) { return Long.compare(this.id, o.id); }
}

put(key, value)
   ↓
hash(key) → 索引 i = (n-1) & hash
   ↓
tab[i] 為 null？ → 是：newNode 放入 → 結束
   ↓ 否
key 相同（hash 同且 equals 真）？ → 是：覆蓋舊值 → 結束
   ↓ 否
節點是 TreeNode？ → 是：treePutTreeVal (紅黑樹插入) → 結束
   ↓ 否 (鏈表)
遍歷鏈表尾部插入 (尾插法)
   ↓
鏈表長度 ≥ 8？ → 是：treeifyBin (嘗試樹化) → 結束
   ↓ 否
結束