HashMap 的容量为什么必须是 2 的幂？负载因子为什么是 0.75？

简化版

容量是 2 的幂，是为了用位运算 (n-1) & hash 代替取模 hash % n——两者在 n 为 2 的幂时结果相同，但位运算快得多，而且能让下标均匀落在 0 ~ n-1。负载因子 0.75 是「空间 vs 时间」的折中：太大冲突多、查询慢，太小浪费内存、扩容频繁；0.75 在泊松分布下能让单桶元素数保持很低，冲突概率小。

详细版

为什么容量是 2 的幂：

位运算代替取模：下标计算是 (n-1) & hash。只有当 n 是 2 的幂时，n-1 的二进制才是「低位全 1」（如 16-1=0b1111），此时 (n-1) & hash 恰好等价于 hash % n，但按位与比取模快很多。
下标分布均匀：n-1 全是 1，hash 的每一个低位都能保留下来参与运算；如果 n 不是 2 的幂（如 15，n-1=0b1110，最低位恒为 0），那所有奇数位下标永远取不到，一半的桶被浪费，冲突翻倍。
扩容迁移高效：翻倍后靠 hash & oldCap 一位就能判断元素「留原地」还是「去 i+oldCap」，无需重新取模。

即使你传入非 2 的幂（如 new HashMap<>(10)），HashMap 也会用 tableSizeFor() 把它向上取整到最近的 2 的幂（10 → 16）。

为什么负载因子是 0.75：

负载因子 = 元素数 / 容量，是扩容的触发线（threshold = 容量 × 负载因子）。
太大（如 1.0）：桶装得满，冲突概率高，链表变长，查询变慢；
太小（如 0.5）：还没装多少就扩容，浪费空间且频繁 rehash；
0.75 是数学与工程折中：在随机哈希下，单桶元素数服从泊松分布，λ=0.75 时桶内出现 8 个元素的概率低到约千万分之六，几乎不会触发树化。

new HashMap<>(10);   // 实际容量被调整为 16
// 阈值 = 16 × 0.75 = 12，放第 13 个元素时扩容到 32

⚠️ threshold 是「元素个数」的阈值，不是「桶被占用数」；size 超过它就扩容，跟有多少桶为空无关。

完整版教学

一、下标计算的本质：把大 hash 压进小数组

key 的 hash 是个 32 位整数（约 40 亿种取值），而数组只有几十上百个桶。要把 hash 映射到 0 ~ n-1，最直观的办法是取模 hash % n。取模能保证结果落在合法范围，但除法运算在 CPU 上相对昂贵，而 HashMap 的 put/get 是超高频操作，这点开销会被放大。

于是设计者用了一个恒等式：当 n 是 2 的幂时，hash % n == hash & (n-1)。按位与是 CPU 最快的指令之一。整个「2 的幂」约束，起点就是为了能安全地用这个恒等式。

二、为什么只有 2 的幂能用位与代替取模

看 n-1 的二进制形态就懂了：

n=16 → n-1=15 → 0b0000_1111   低 4 位全 1
n=32 → n-1=31 → 0b0001_1111   低 5 位全 1
n=15 → n-1=14 → 0b0000_1110   最低位是 0 ！

(n-1) & hash 是「用 n-1 当掩码，保留 hash 的低若干位」。只有 n-1 全是 1，才能完整保留低位、且结果均匀覆盖 0 ~ n-1。若 n=15，掩码 0b1110 的最低位恒为 0，意味着 & hash 的结果最低位永远是 0——所有下标都是偶数，1、3、5、7…这些桶永远空着，实际可用桶少一半，冲突率直接翻倍。

三、用数字验证「位与 = 取模」

拿 n=16、hash=1234 实算一遍，两种算法结果必须一致：

1234 % 16      = 1234 - 77×16 = 1234 - 1232 = 2
1234 & (16-1)  = 0b100_1101_0010 & 0b0000_1111 = 0b0010 = 2   ✓
再看 hash=1000：
1000 % 16      = 8
1000 & 15      = 0b11_1110_1000 & 0b1111 = 0b1000 = 8         ✓

两者恒等，但位与省掉了除法。注意：这个等式只对非负数、且 n 为 2 的幂成立；HashMap 里 hash 经扰动后当作无符号处理，正好满足。

四、tableSizeFor：非 2 的幂怎么办

你 new HashMap<>(10) 传了个非 2 的幂，HashMap 不会将就，而是用 tableSizeFor() 把它「向上取整到最近的 2 的幂」，保证约束永远成立：

你传入	实际初始容量
1	1
6	8
10	16
17	32
1000	1024

其实现是一串移位或运算：把最高位 1 右边的位全部填 1（得到 0b1111...），再 +1，就得到大于等于它的最小 2 的幂。所以「必须是 2 的幂」是 HashMap 强制维护的内部不变量，你无法绕过。

五、负载因子 0.75 背后的泊松分布

负载因子决定「装多满才扩容」。它本质是在两条曲线间找平衡点：

调高（趋近 1）：省内存（桶利用率高），但冲突概率随之上升，链表变长，get 变慢；
调低（趋近 0.5）：查询快（几乎无冲突），但一半空间闲置，且很快触发扩容拷贝。

JDK 源码注释给出了理论依据：在随机哈希、负载因子 0.75 下，某个桶里恰好有 k 个元素的概率服从泊松分布 λ=0.5：

桶内元素数 k    概率
0            0.60653
1            0.30327
2            0.07582
3            0.01264
...
8            0.00000006   ← 约千万分之六

也就是说，正常使用下一个桶几乎不可能堆到 8 个元素，链表极短，查询贴近 O(1)；而树化（阈值 8）几乎只在哈希被恶意攻击时才触发。0.75 = 3/4，还有个工程小优点：容量 × 0.75 在容量为 4 的倍数时是整数，位运算就能算（cap - (cap >>> 2)），不引入浮点。

六、负载因子调大调小的实际后果

负载因子	内存占用	冲突/链表长度	扩容频率	适用场景
0.5	高（桶多空着）	很少冲突，查询最快	频繁	查询极敏感、内存充裕
0.75（默认）	平衡	冲突少	适中	绝大多数场景
1.0	最省	冲突明显增多	最少	内存极紧张、能容忍慢查询

大多数情况不要动默认值。真要改，也应连同初始容量一起规划：已知要放 200 个元素，与其调负载因子，不如直接 new HashMap<>(256)（200/0.75≈267，向上取 512 更稳），从源头避免扩容。

记忆钩子：2 的幂是为了「与运算取模 + 分布均匀 + 扩容省算」，0.75 是为了「泊松分布下桶几乎不堆积」——一个管定位，一个管扩容时机。

七、常见误区与追问

误区：容量必须是 2 的幂，所以我 new 的时候一定要传 2 的幂。 不必，tableSizeFor 会自动向上取整；传 10 会变 16，功能正确，只是浪费了你以为的精确控制。
误区：负载因子越小越好，冲突越少。 小到 0.5 确实冲突少，但内存翻倍、扩容更频繁；0.75 是综合最优，盲目调小得不偿失。
误区：threshold 是桶被占满的数量。 它是元素总数（size）的阈值，等于 容量 × 负载因子，与有多少桶空闲无关。
误区：hash % n 和 (n-1) & hash 永远相等。 只有 n 是 2 的幂且按无符号处理时才相等；n 非 2 的幂时二者结果不同。
追问：为什么默认初始容量是 16 而不是别的？ 16 是「不太小（避免刚放几个就扩容）又不太浪费」的经验值，且是 2 的幂；配合 0.75，前 12 个元素无需扩容。
追问：负载因子设成 1.0 会怎样？ 桶几乎装满才扩容，冲突概率明显上升，链表变长甚至更容易树化，查询变慢，用空间换来的是时间损失。
追问：能不能既传初始容量又传负载因子？ 可以，new HashMap<>(initialCapacity, loadFactor)；threshold 会按二者乘积计算，初始容量仍会被取整到 2 的幂。

八、加强记忆

两个魔法数字各司一职。「2 的幂」服务于定位：它让 n-1 变成「低位全 1」的掩码，于是 (n-1) & hash 既等价于取模又快得多，还保证每个桶都可能被选中、扩容时靠一位判断去留——你传非 2 的幂，tableSizeFor 也会强行帮你取整，这是不可绕过的内部不变量。「0.75」服务于扩容时机：它把「省内存」和「少冲突」调到平衡点，在泊松分布下让单桶堆到 8 个元素的概率低到千万分之几，正常使用几乎不树化、查询贴近 O(1)，还能用 cap - (cap>>>2) 纯整数算阈值。记住一句话：「幂管定位、0.75 管火候」，再补「预估规模就直接设容量，别去动负载因子」，这题就稳了。

简化版

详细版