深度解析 HashMap 核心原理與手寫實現

HashMap 是 Java 開發中使用頻率最高的集合類之一，其底層結構巧妙結合了數組與鏈表（JDK 1.8 後引入紅黑樹），兼顧了查詢、插入、刪除的高效能。本文將從數據結構、核心方法、性能優化三個維度深度解析，並附上手寫簡易版 HashMap 的關鍵代碼。

核心數據結構：數組 + 鏈表

HashMap 內部維護一個 Entry[] table 數組，每個位置（桶）指向一條鏈表。Entry 節點封裝 key、value、hash 及 next 指針，形成鏈表結構：

transient Entry[] table;

static class Entry<K,V> {
    final K key;
    V value;
    Entry<K,V> next;
    final int hash;
    // ...
}

核心流程解析

Put 操作：計算索引 → 遍歷鏈表 → 覆蓋或尾插

public V put(K key, V value) {
    int hash = hash(key);
    int i = indexFor(hash, table.length);
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    addEntry(hash, key, value, i); // 頭插法（JDK 1.7）或尾插法（JDK 1.8+）
    return null;
}

Get 操作：同樣計算索引 → 遍歷鏈表比對 key

public V get(Object key) {
    int hash = hash(key);
    for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
            return e.value;
    }
    return null;
}

性能優化兩大殺手鐧

1. 擾動函數：降低 Hash 碰撞

JDK 1.7 使用多次無符號右移異或：

static int hash(int h) {
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

JDK 1.8 簡化為：h ^ (h >>> 16)，使高位參與運算，大幅降低碰撞概率。

2. 動態擴容：負載因子與 2 倍擴容

• 默認初始容量 16，負載因子 0.75。
• 當 size > threshold (capacity * loadFactor) 時觸發擴容。
• 新建 2 倍大小的數組，重新計算所有元素索引遷移（Rehash），耗時操作。
• 最佳實踐： 預估數據量時，通過構造函數指定 initialCapacity 避免頻繁擴容。

手寫簡易 HashMap 關鍵點

作者提供了 GitHub 完整代碼（github.com/xcr1234/my-java），核心邏輯包括：

• 自定義 Node<K,V> 節點類
• 實現 put、get、resize 方法
• 使用 Math.abs(key.hashCode()) % capacity 計算索引（教學演示用，生產環境建議用位運算）

總結

理解 HashMap 底層原理，不僅是面試必考點，更能指導實際開發：預估容量、選擇合適的 Key（實現良好的 hashCode/equals）、避免在高併發下使用非線程安全的 HashMap（改用 ConcurrentHashMap）。手寫實現是深化理解的最佳途徑，建議讀者嘗試完善擴容、紅黑樹轉換等進階功能。