HashMap 深度剖析：核心原理、擴容機制與性能調優

核心結構：數組 + 鏈表/紅黑樹

JDK 8 之前：Node[] table + 單向鏈表解決哈希衝突。
JDK 8+：鏈表長度 ≥ 8 且數組長度 ≥ 64 時轉為紅黑樹，退化為 O(log n)。

關鍵屬性

• DEFAULT_INITIAL_CAPACITY = 16（必為 2 的冪）
• DEFAULT_LOAD_FACTOR = 0.75f：負載因子，平衡空間與查找時間
• threshold = capacity * loadFactor：擴容閾值，默認 12
• TREEIFY_THRESHOLD = 8、UNTREEIFY_THRESHOLD = 6、MIN_TREEIFY_CAPACITY = 64

put 核心流程

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node[] tab; Node p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length; // 惰性初始化

    // 1. 計算索引：(n-1) & hash
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null); // 空槽直接放入
    else {
        Node e; K k;
        // 2. 衝突處理：遍歷鏈表/樹
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
            e = p; // 鍵相同，覆蓋值
        else if (p instanceof TreeNode)
            e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
        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;
            }
        }
        if (e != null) { // 存在舊鍵
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue; // 返回舊值
        }
    }
    ++modCount;
    if (++size > threshold)
        resize(); // 擴容
    afterNodeInsertion(evict);
    return null;
}

hash 方法與索引計算

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// 索引：(n - 1) & hash  —— 等價 hash % n 但更快，要求 n 為 2 的冪

高 16 位參與運算減少低位差異導致的碰撞（因 hashCode 通常高位變化小）。

擴容機制

• 新容量 = 舊容量 × 2
• 重新計算每個節點索引：(e.hash & oldCap) == 0 ? newIdx : newIdx + oldCap（原索引或原索引+oldCap），避免全量重新 hash
• 同桶節點順序保持（JDK 7 反轉導致併發死循環，JDK 8 修復）

性能調優實戰

1. 預估容量：new HashMap<>(expectedSize) 或 new HashMap<>((int)(expectedSize/0.75f)+1) 避免多次擴容
2. 鍵不可變：String、Integer 等最終類最佳；自定義鍵必須正確實現 hashCode()/equals() 且創建後不變
3. 避免鍵碰撞攻擊：JDK 8+ 紅黑樹緩解，極端場景可用 -Djdk.map.althashing.threshold=0 啟用替代哈希
4. 並發場景：絕不使用 HashMap，改用 ConcurrentHashMap 或 Collections.synchronizedMap
5. 遍歷效率：entrySet() 遍歷 Map.Entry 避免二次 get；JDK 8+ forEach((k,v)->...) 內部優化

何時自定義 Map？

僅當：

• 極簡場景（固定鍵值、無擴容、無併發）需極致性能
• 特殊語義（LRU、有序、多值）既有實現不滿足
• 教學/面試演示

其餘情況直接用 JDK 或成熟庫（Guava、FastUtil、Eclipse Collections）。