您现在的位置：程式碼之家 >> 編程語言 > >> Java 程式設計 >> Java 相關知識

HashMap 核心原理深度解析：JDK 8 併發優化與擴容機制

編輯：Java 相關知識

HashMap 是 Java 集合框架中使用頻率最高、面試考察最深的數據結構。本文基於 JDK 8 源碼，系統剖析其底層存儲、核心操作流程、紅黑樹轉換、擴容優化及關鍵面試考點。

一、核心屬性與數據結構

// 默認初始容量：16 (必須是 2 的冪次)
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

// 默認加載因子：0.75 (空間與時間的平衡點)
static final float DEFAULT_LOAD_FACTOR = 0.75f;

// 鏈表轉紅黑樹閾值：8
static final int TREEIFY_THRESHOLD = 8;

// 紅黑樹退化為鏈表閾值：6
static final int UNTREEIFY_THRESHOLD = 6;

// 數組長度達到 64 才允許樹化 (避免小數組過早樹化)
static final int MIN_TREEIFY_CAPACITY = 64;

底層結構：Node<K,V>[] table 數組 + 鏈表/紅黑樹。數組每個位置稱為「桶」。

二、hash() 方法：擾動函數設計

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

設計意圖：高 16 位不變，低 16 位與高 16 位異或。使 hashCode() 的高位信息參與到下標計算中，減少哈希碰撞，特別是在數組長度較小（如 16、32）時。

三、下標計算：位運算替代取模

// n 為數組長度(2的冪次)，n-1 二進制全為1
// (n-1) & hash 等價於 hash % n，但效率高得多
int index = (n - 1) & hash;

四、putVal 核心流程解析

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    
    // 1. 延遲初始化：首次 put 時創建數組
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    
    // 2. 計算下標，桶為空直接放入
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        // 3. 節點已存在(key相同)，覆蓋值
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 4. 紅黑樹節點，調用樹插入邏輯
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 5. 鏈表節點，遍歷鏈表
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // 達到樹化閾值，轉紅黑樹
                    if (binCount >= TREEIFY_THRESHOLD - 1)
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // 6. 節點存在，替換值並返回舊值
        if (e != null) {
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    // 7. 尺寸檢查，擴容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

五、get 獲取流程

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 && 
        (first = tab[(n - 1) & hash]) != null) {
        // 1. 首節點命中
        if (first.hash == hash && 
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        // 2. 後續節點查找
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                if (e.hash == hash && 
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

六、resize 擴容機制：JDK 8 關鍵優化

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) { // 達到最大容量
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 擴容為 2 倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // threshold 也翻倍
    }
    // ... 其他初始化分支
    
    // 核心優化：重新計算位置
    // (n - 1) & hash 中，n 變為 2n，只多一個 bit 參與運算
    // 元素新位置要么不變(index)，要么移動到 index + oldCap
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    // ... 遷移邏輯：分為 lo 列表(原位置) 和 hi 列表(原位置+oldCap)
}

遷移邏輯精髓：利用 e.hash & oldCap 判斷該 bit 是 0 還是 1，決定節點留在原桶還是移動到新桶，避免重新計算完整 hash，極大提升擴容性能。

七、面試高頻考點總結

問題	核心回答要點
HashMap 特點	基於 Map 接口、允許 null key/value、非線程安全、不保證順序
工作原理	hash(key) → index → 桶為空放入/碰撞鏈表/樹化/覆蓋/擴容
get/put 原理	hash 定位桶 → equals 定位節點
hash 實現意圖	高低位異或，讓高位參與下標計算，減少碰撞
擴容觸發條件	size > threshold (capacity * loadFactor)
JDK 8 擴容優化	不重新計算 hash，按 hash & oldCap 分流到原位或原位+oldCap
為何負載因子 0.75	泊松分布下，碰撞概率與空間利用率的數學平衡點
樹化閾值 8 的由來	泊松分布下，鏈表長度達 8 的概率極低(<0.00000006)，樹化收益大於成本
線程不安全表現	JDK 7 頭插法擴容導致鏈表成環(死循環)；JDK 8 尾插法避免成環但仍有數據覆蓋丟失

八、最佳實踐建議

預估數據量，指定 initialCapacity 避免頻繁擴容：new HashMap<>((int)(expectedSize / 0.75) + 1)
Key 類正確重寫 hashCode() 與 equals()，保持一致性契約
多線程環境使用 ConcurrentHashMap 或 Collections.synchronizedMap()
避免在 Key 中使用可變對象，或修改 Key 後導致無法獲取