Java HashMap 核心原理深度解析：哈希桶、鏈表、紅黑樹與擴容機制

HashMap 是 Java 集合框架核心成員，面試高頻考點，生產環境高頻使用。本文從源碼層面深度解析 JDK 8 HashMap 的存儲結構、put/get 流程、擴容機制、紅黑樹轉換與線程安全陷阱。

核心數據結構

// 靜態內部類：鍵值對節點
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;      // 鏈表指針
    // 樹節點擴展字段 (JDK 8)
    Node<K,V> left, right, parent;
    boolean red;
}

• table：Node<K,V>[] 數組，長度永遠是 2 的冪次
• 桶：數組每個位置，可掛載鏈表或紅黑樹
• hash：鍵的雜湊值經擾動函數處理後的值

雜湊計算與索引定位

// 擾動函數：高 16 位參與運算，減少碰撞
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

// 索引計算：(n - 1) & hash，等價於 hash % n (n 為 2 的冪次)
static int indexFor(int hash, int length) {
    return hash & (length - 1);
}

put 流程深度解析

public V put(K key, V value) {
    // 1. null 鍵特殊處理，存放 table[0]
    if (key == null) return putForNullKey(value);
    
    // 2. 計算雜湊、定位桶索引
    int hash = hash(key);
    int i = indexFor(hash, table.length);
    
    // 3. 遍歷桶內節點
    for (Node<K,V> e = table[i]; e != null; e = e.next) {
        // 4. 雜湊相等且 key 相等 → 覆蓋舊值
        if (e.hash == hash && (e.key == key || key.equals(e.key))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    
    // 5. 未找到 → 新增節點
    modCount++;
    addEntry(hash, key, value, i);
    return null;
}

void addEntry(int hash, K key, V value, int bucketIndex) {
    // 擴容檢查
    if ((size >= threshold) && (table[bucketIndex] != null)) {
        resize(2 * table.length);
        bucketIndex = indexFor(hash, table.length); // 重新計算索引
    }
    createEntry(hash, key, value, bucketIndex);
}

void createEntry(int hash, K key, V value, int bucketIndex) {
    Node<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Node<>(hash, key, value, e); // 頭插法
    size++;
}

JDK 8 關鍵優化：鏈表轉紅黑樹

目的：極端碰撞情況下，查詢複雜度從 O(n) 降為 O(log n)，防止 HashDoS 攻擊。

擴容機制

void resize(int newCapacity) {
    Node<K,V>[] oldTable = table;
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }
    
    Node<K,V>[] newTable = new Node[newCapacity];
    transfer(newTable); // 核心遷移邏輯
    table = newTable;
    threshold = (int)(newCapacity * loadFactor);
}

void transfer(Node<K,V>[] newTable) {
    for (Node<K,V> e : table) {
        while (e != null) {
            Node<K,V> next = e.next;
            // 重新計算索引：高位為 0 留原位，為 1 移至 newIndex = oldIndex + oldCapacity
            int newIndex = (e.hash & (newTable.length - 1));
            e.next = newTable[newIndex];
            newTable[newIndex] = e; // 頭插法 (JDK 7) / 尾插法 (JDK 8)
            e = next;
        }
    }
}

關鍵差異：JDK 7 頭插法導致並發擴容形成環狀鏈表 (死循環)；JDK 8 尾插法保持原序，避免環形。

get 流程

public V get(Object key) {
    if (key == null) return getForNullKey();
    int hash = hash(key);
    Node<K,V> e = table[indexFor(hash, table.length)];
    while (e != null) {
        if (e.hash == hash && (e.key == key || key.equals(e.key)))
            return e.value;
        e = e.next; // 或樹遍歷
    }
    return null;
}

關鍵屬性與預設值

線程安全陷阱與替代方案

最佳實踐清單

• 預估數據量，指定初始容量 new HashMap<>(expectedSize)，減少擴容
• 鍵類型正確實作 hashCode()/equals()，不可變對象最佳
• 避免在多線程環境直接使用 HashMap
• JDK 8+ 享受紅黑樹防禦，但仍需警惕惡意構造碰撞鍵
• 頻繁讀寫場景考慮 ConcurrentHashMap 或 ReadWriteLock + HashMap

HashMap 以「數組 + 鏈表/紅黑樹」經典結構，配合擾動函數、負載因子、擴容遷移、樹化退化等精妙機制，實現了極致的單線程效能。理解其內核，是進階 Java 工程師的必修課。