在 Java 面试中，有一个经典问题：为什么 HashMap 的容量必须是 2 的 n 次方？ 这背后涉及位运算优化、哈希冲突降低、扩容效率提升等多个设计哲学。本文将深入源码，从数学原理、性能测试、实际案例三个维度，彻底讲透这个设计。

1. 核心原因速览

2. 原因一：位运算替代取模（核心性能优化）

2.1 取模运算的性能问题

在 HashMap 中，需要根据 hash 值计算数组索引：index = hash % capacity

// 传统取模运算（慢）
int index = hash % 16;  // 除法运算，CPU耗时 ~20-30个时钟周期

// 位运算（快）
int index = hash & (16 - 1);  // 与运算，CPU耗时 ~1个时钟周期

性能对比测试：

2.2 数学证明：当 n = 2^k 时，等价成立

// 证明：当 capacity = 2^n 时
// hash % capacity = hash & (capacity - 1)

// 举例：capacity = 16 (2^4)，binary = 10000
// capacity - 1 = 15，binary = 01111

// hash = 25 (binary: 11001)
// 25 % 16 = 9
// 25 & 15 = 11001 & 01111 = 01001 = 9 ✅

// hash = 100 (binary: 1100100)
// 100 % 16 = 4
// 100 & 15 = 1100100 & 0001111 = 0000100 = 4 ✅

2.3 源码验证

// HashMap 源码中的索引计算
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 关键：用位运算代替取模
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    // ...
}

3. 原因二：扩容时元素位置可预测（无需重新哈希）

3.1 核心规律

当容量从 oldCap 扩容到 oldCap * 2 时，元素的新索引只有两种可能：

• 原索引（当 hash & oldCap == 0）
• 原索引 + oldCap（当 hash & oldCap != 0）

// 扩容时的索引判断
if ((e.hash & oldCap) == 0) {
    // 低位：索引不变
    newTab[j] = loHead;
} else {
    // 高位：新索引 = 原索引 + oldCap
    newTab[j + oldCap] = hiHead;
}

3.2 原理图解

3.3 数学推导

// 假设 oldCap = 8 (1000)
// 原索引 = hash & (8-1) = hash & 0111

// 新容量 newCap = 16 (10000)
// 新索引 = hash & (16-1) = hash & 01111

// 观察 hash 的第4位（8对应的位）：
// - 如果第4位 = 0：新索引 = 原索引
// - 如果第4位 = 1：新索引 = 原索引 + 8

// 验证：
// hash=5 (0101)，第4位=0 → 原索引=5，新索引=5 ✅
// hash=13 (1101)，第4位=1 → 原索引=5，新索引=13=5+8 ✅

4. 原因三：哈希分布更均匀

4.1 当 capacity 不是 2 的幂时的问题

// 假设 capacity = 10（不是2的幂）
// capacity - 1 = 9 = 1001（二进制）

// 索引 = hash & 1001
// 只有第0位和第3位参与计算，其他位永远为0

哈希碰撞对比：

4.2 极端案例演示

// 容量为 15 时的问题
int capacity = 15;
int mask = capacity - 1;  // 14 = 1110

// 测试不同 hash 值
int[] hashs = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
for (int h : hashs) {
    int index = h & mask;
    System.out.println("hash=" + h + " → index=" + index);
}
// 结果：所有 hash 值都会映射到偶数索引！
// hash=1 → index=0
// hash=3 → index=2
// hash=5 → index=4
// 奇数索引（1,3,5,7,9,11,13）永远为空

5. 原因四：配合扰动函数，充分利用高位信息

5.1 扰动函数设计

// HashMap 的哈希计算（JDK8）
static final int hash(Object key) {
    int h;
    // 高16位与低16位异或，混合高位信息
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

5.2 为什么需要扰动函数 + 2的幂？

如果容量不是2的幂：

• 扰动函数混合的高位信息可能被浪费
• 某些位永远不参与索引计算

6. 完整流程图：索引计算全过程

7. 特殊情况处理：容量为 1 的情况

// HashMap 最小容量为 1（通过 tableSizeFor 保证至少为 1）
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;
}

容量为 1 时的索引计算：

// capacity = 1, capacity-1 = 0
// 索引 = hash & 0 = 0（永远为0）
// 此时 HashMap 退化为一个链表，性能极差

结论：虽然最小容量是 1，但实际使用中应避免极小容量。

8. 性能实测对比

8.1 测试代码

public class CapacityTest {
    // 测试不同容量下的索引分布均匀性
    public static void testDistribution(int capacity, int testCount) {
        int mask = capacity - 1;
        int[] buckets = new int[capacity];
        
        Random random = new Random();
        for (int i = 0; i < testCount; i++) {
            int hash = random.nextInt();
            int index = hash & mask;
            buckets[index % capacity]++;
        }
        
        // 计算标准差（越小越均匀）
        double avg = testCount * 1.0 / capacity;
        double variance = Arrays.stream(buckets)
            .mapToDouble(v -> Math.pow(v - avg, 2))
            .average().orElse(0);
        System.out.printf("capacity=%d, 标准差=%.2f%n", capacity, Math.sqrt(variance));
    }
    
    public static void main(String[] args) {
        testDistribution(16, 100000);   // 2的幂
        testDistribution(15, 100000);   // 非2的幂
        testDistribution(17, 100000);   // 2的幂+1
    }
}

8.2 测试结果

9. 常见面试追问

Q1：HashMap 允许用户指定初始容量，如果传入不是2的幂会怎样？

A：tableSizeFor() 方法会将容量调整为大于等于该数的最小2的幂。

// 传入 10，实际容量为 16
Map<String, String> map = new HashMap<>(10);
// 源码中调用 tableSizeFor(10) 返回 16

Q2：为什么不直接用 hash % capacity 而要用位运算？

A：性能差异巨大。位运算比取模快约 10 倍，在 HashMap 这种高频调用的场景下，性能提升显著。

Q3：负载因子和2的幂有什么关系？

A：负载因子控制扩容时机，而 2 的幂保证扩容后元素只需判断一个 bit 位就能确定新位置，无需重新计算完整 hash，大幅提升扩容效率。

Q4：ConcurrentHashMap 也是用 2 的幂吗？

A：是的。ConcurrentHashMap 同样要求容量为 2 的幂，索引计算也用 (n-1) & hash，但它的并发控制机制不同（CAS + synchronized）。

10. 设计思想总结

11. 完整对比总结表

12. 一句话记忆

2 的幂，位运算快 10 倍；扩容移位定位置，哈希均匀碰撞少。

口诀：

容量取二幂，位运算代替取模费。
n 减一全是1，哈希散列真均匀。
扩容只看一个位，原来位置或加旧容量。
扰动混合高低位，最终索引分布美。

如果你彻底理解了为什么 HashMap 容量必须是 2 的幂，欢迎点赞、收藏、转发！有任何疑问，评论区一起交流~