HashMap 初始容量計算演進：從 JDK 1.7 循環位移到 JDK 1.8 位運算優化

構造函數簽名

public HashMap(int initialCapacity, float loadFactor)

核心邏輯：根據 initialCapacity 計算 大於等於該值的最小 2 的 N 次方 作為實際桶數組容量。

為什麼容量必須是 2 的冪？

因為 index = (n - 1) & hash 取模運算要求 n 為 2 的冪，否則分佈不均。詳細證明見 此文。

JDK 1.7 及之前：循環左移

int capacity = 1;
while (capacity < initialCapacity)
    capacity <<= 1;

• 每次迴圈：比較 + 位移，共 2 * N 次操作（N 為目標冪次）。
• 當 initialCapacity > 64 時效率明顯低於新版。

JDK 1.8：無分支位運算優化

static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

原理圖解（以 9 位二進制 1xxxxxxx 為例）

1. n = cap - 1 → 低位至少有一個 1 變為 0，其餘不變。
2. n |= n >>> 1 → 高位 1 向右傳播一位，變為 11xxxxxx。
3. n |= n >>> 2 → 傳播兩位 → 1111xxxx。
4. n |= n >>> 4 → 11111111（所有低位變 1）。
5. 以此類推至 >> 16 覆蓋 32 位 int 範圍。
6. n + 1 → 進位變為 100000000，即下一個 2 的冪。

特殊情況：輸入本身就是 2 的冪

例 cap = 1000（二進制），n = 111，位運算後仍為 111，+1 還原為 1000，完美支援。

性能對比

結論：當指定容量 > 64（2^6）時，JDK 1.8 算法顯著更快。

進一步優化：輸入即 2 的冪時直接返回

static final int tableSizeFor(int cap) {
    int n = cap - 1;
    if ((cap & n) == 0) { // 經典判斷 2 的冪：n & (n-1) == 0
        return (cap >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : cap;
    }
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

避免對已經是 2 的冪的輸入做無用位運算，極小優化但體現工程嚴謹。