Java HashMap 核心源碼深度解析：容量擴容、負載因子、tableSizeFor 位運算藝術

HashMap 源碼級剖析：初始容量、負載因子、擴容閾值計算與位運算神技

HashMap 是 Java 面試必考、生產環境最高頻集合。本文直擊源碼（JDK 8/11/17 通用），解析 DEFAULT_INITIAL_CAPACITY、DEFAULT_LOAD_FACTOR、構造器參數校驗、tableSizeFor 位運算找最近 2 的冪次，揭示性能調優關鍵參數。

一、核心常量與默認值

// 默認初始容量：16 = 1 << 4
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 

// 最大容量：2^30
static final int MAXIMUM_CAPACITY = 1 << 30;

// 默認負載因子：0.75f（時間/空間折中）
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;

二、構造器參數校驗與閾值初始化

public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " + loadFactor);

    this.loadFactor = loadFactor;
    // 關鍵：threshold = tableSizeFor(initialCapacity)
    // 即：擴容閾值 = 首個 >= initialCapacity 的 2 的冪次
    this.threshold = tableSizeFor(initialCapacity);
}

注意：構造器**不創建 table 數組**，首次 put 時才 resize() 初始化。

三、tableSizeFor 位運算神技：O(1) 找最近 2 的冪次

static final int tableSizeFor(int cap) {
    int n = cap - 1;           // 關鍵：cap 為 2 的冪時不變大
    n |= n >>> 1;              // 最高位 1 向右傳播 1 位
    n |= n >>> 2;              // 傳播 2 位
    n |= n >>> 4;              // 傳播 4 位
    n |= n >>> 8;              // 傳播 8 位
    n |= n >>> 16;             // 傳播 16 位（int 32 位足夠）
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

逐步演示：cap = 10 → 返回 16

精髓：通過「最高位 1 向右填滿 1」+ 1，得到下一個 2 的冪次。無分支、無循環、純位運算，極致高效。

四、負載因子與擴容機制

• threshold = (int)(capacity * loadFactor)
• 當 size >= threshold 觸發 resize()：容量翻倍（newCap = oldCap << 1），重新計算索引 (n - 1) & hash
• 0.75 為何是黃金分割？：泊松分布下，碰撞概率與空間浪費平衡；0.5 空間浪費大，1.0 碰撞劇增

五、性能調優實戰建議

1. 預估數據量，指定初始容量：
   Map map = new HashMap<>((int)(expectedSize / 0.75f) + 1);
   避免多次擴容、重新哈希、數組複製開銷
2. 避免負載因子過大：除非極度內存受限且讀多寫少，否則**不要改動 loadFactor**
3. 鍵對象高質量 hashCode：不可變對象、均勻分佈，減少碰撞、樹化概率
4. 並發場景用 ConcurrentHashMap：HashMap 非線程安全，多線程 put 會導致鏈表成環、CPU 100%

六、擴容後索引重新計算優化（JDK 8+）

// 舊索引：oldIdx = (oldCap - 1) & hash
// 新索引：newIdx = (newCap - 1) & hash
// 因為 newCap = oldCap * 2，所以新索引只有兩種可能：
// 1. 同舊索引（hash 的新高位為 0）
// 2. 舊索引 + oldCap（hash 的新高位為 1）
// 由此實現「不重新遍歷整個鏈表」的高效遷移

七、總結

掌握 HashMap 容量模型、負載因子、位運算找 2 的冪次，是寫出高性能 Java 代碼、通過大廠面試的核心基本功。