HashMap 核心原理深度解析：put/get 流程、擴容機制與鏈表紅黑樹轉換

核心結構：陣列 + 鏈表 + 紅黑樹 (JDK 8+)

transient Node[] table; // 主陣列，長度永遠是 2 的冪次

static class Node implements Map.Entry {
    final int hash;
    final K key;
    V value;
    Node next; // 鏈表指針
    // JDK 8 新增：TreeNode 繼承 Node，增加紅黑樹欄位
}

關鍵參數

put 流程深度剖析 (JDK 8)

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;
    
    // 1. 延遲初始化：首次 put 時才建立陣列
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    
    // 2. 計算桶索引：(n-1) & hash
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null); // 空桶直接放入
    else {
        Node e; K k;
        // 3. 遍歷桶內結構（鏈表或紅黑樹）
        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);
                    // 4. 鏈表長度達閾值 → 樹化
                    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;
            }
        }
        
        // 5. 覆蓋舊值
        if (e != null) {
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    // 6. 擴容檢查
    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);
}

將 hashCode 高 16 位與低 16 位異或，使高位資訊參與索引計算（因 (n-1) & hash 僅用低位）。

get 流程：同邏輯查找

public V get(Object key) {
    Node e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node getNode(int hash, Object key) {
    Node[] tab; Node first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                return ((TreeNode)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;
}

擴容機制：2 倍擴容 + 重新分佈

final Node[] resize() {
    Node[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) { // 1 << 30
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // 雙倍閾值
    }
    else if (oldThr > 0)
        newCap = oldThr;
    else {
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); // 12
    }
    
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    Node[] newTab = (Node[])new Node[newCap];
    table = newTab;
    
    // 核心：重新分佈節點
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node e = oldTab[j];
            if (e == null) continue;
            if (e.next == null) // 單節點直接遷移
                newTab[e.hash & (newCap - 1)] = e;
            else if (e instanceof TreeNode)
                ((TreeNode)e).split(this, newTab, j, oldCap); // 紅黑樹分裂
            else { // 鏈表分裂：保持原序
                Node loHead = null, loTail = null;
                Node hiHead = null, hiTail = null;
                Node 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;
                    }
                } while ((e = next) != null);
                if (loTail != null) {
                    loTail.next = null;
                    newTab[j] = loHead;
                }
                if (hiTail != null) {
                    hiTail.next = null;
                    newTab[j + oldCap] = hiHead;
                }
            }
        }
    }
    return newTab;
}

擴容優化：避免重新計算 hash

利用 e.hash & oldCap 判斷高位，決定新索引是 j 還是 j + oldCap，無需重新 hash() 計算，且保持鏈表原序（避免多執行緒舊版本死循環）。

紅黑樹轉換條件與意義

為何閾值 8/6？泊松分佈下，桶長度達 8 機率極低（< 0.0000001），樹化收益大於成本；6 留有緩衝避免頻繁震盪。

效能調優實戰建議

1. 預估大小，避免擴容：new HashMap<>(expectedSize)，構造函數會計算 tableSizeFor(expectedSize / 0.75f + 1)
2. Key 正確實現 hashCode/equals：不可變物件最佳，避免自定義 Key 導致碰撞
3. 避免 null Key：雖支援（固定索引 0），但語意模糊，建議用 Optional
4. 高併發用 ConcurrentHashMap：HashMap 非執行緒安全，多執行緒 put 可能導致鏈表死循環（JDK 7）或資料丟失
5. 初始化容量設為 2 的冪次：tableSizeFor 會自動向上取最接近的 2 冪

總結

HashMap 以陣列 + 鏈表/紅黑樹實現 O(1) 平均查找。核心精華在於：hash() 擾亂算法、索引計算、擴容分裂保持順序、樹化閾值權衡。理解這些機制，不僅能寫出高效程式碼，更能在面試與疑難排查中游刃有餘。