为什么 HashMap 在 Java 中扩容时采用 2 的 n 次方倍？

HashMap 为什么采用 2 的 n 次方倍扩容？

【核心定义】

HashMap 采用 2 的 n 次方倍扩容，主要是为了优化哈希索引的计算效率，通过位运算替代取模运算，同时保证元素在扩容后能够均匀分布。

【关键要点】

计算效率优化：使用 (n - 1) & hash 替代 hash % n，位运算比取模运算快得多
分布均匀性：当容量为 2 的幂时，(n - 1) 的二进制是全 1（如 15=1111），与哈希值做与运算能保留低位信息，减少哈希冲突
扩容迁移优化：扩容时（2 倍扩容），元素的新位置要么在原索引处，要么在 原索引 + 原容量 处，可以通过位运算快速判断

【深度推导/细节】

哈希索引计算原理

// 实际计算索引的代码
index = (n - 1) & hash

// 示例：容量 n=16（二进制 10000）
// n-1 = 15（二进制 01111）
// hash 值：任意 32 位整数
// 与运算结果：只保留 hash 的低 4 位

为什么必须是 2 的幂？

数学原理：当 n 是 2 的幂时，n-1 的二进制形式是连续的 1
- n=16: n-1=15 (01111)
- n=32: n-1=31 (11111)
均匀分布保证：连续的 1 能确保哈希值的每一位都参与索引计算，减少冲突

扩容时的元素迁移

// 扩容时判断元素新位置的逻辑
if ((e.hash & oldCap) == 0) {
    // 新索引 = 原索引
} else {
    // 新索引 = 原索引 + 原容量
}

// 原理：oldCap 是 2 的幂，其二进制只有一位是 1
// 例如 oldCap=16（10000），判断 hash 值的第 5 位是 0 还是 1

Step-by-Step 扩容过程：

创建新数组：容量变为原来的 2 倍（保持 2 的幂）
遍历旧数组：对每个桶中的元素重新计算位置
快速定位：利用 (e.hash & oldCap) == 0 判断
- 为 0：元素留在原索引位置
- 不为 0：元素移动到 原索引 + oldCap 位置
链表/树迁移：保持原有顺序或重新平衡

【关联/对比】

HashMap vs HashTable

容量设计：HashMap 强制容量为 2 的幂（通过 tableSizeFor 方法），HashTable 不要求
计算方式：HashMap 用位运算，HashTable 用取模运算

不同版本的实现

Java 7：使用 indexFor(hash, length) 方法显式计算索引
Java 8+：直接内联计算 (n - 1) & hash
扩容时机：Java 8 引入了树化优化，但扩容机制的核心逻辑不变

『面试官追问』

可能的问题：

如果不是 2 的幂会怎样？
- 计算索引时会出现某些位置永远无法被访问到的”空洞”
- 元素分布不均匀，某些桶可能一直为空，某些桶过度拥挤
为什么选择 2 的幂而不是其他数？
- 计算机底层是二进制，2 的幂最符合硬件特性
- 位运算是 CPU 最基本的操作，效率最高

HashMap 如何保证容量是 2 的幂？

// Java 8 中的 tableSizeFor 方法
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;
}

这个方法将任意正整数转换为不小于它的最小 2 的幂

扩容时为什么元素要么在原位置，要么在”原位置+原容量”？
- 数学证明：newIndex = hash & (2n - 1) = hash & (n - 1) + (hash & n)
- 当 hash & n == 0 时，新索引等于原索引
- 当 hash & n == n 时，新索引等于原索引 + n

性能对比数据

位运算 vs 取模：位运算比取模快 5-10 倍（取决于 CPU 架构）
扩容成本：2 的幂扩容使得只有约 50% 的元素需要移动，降低了扩容开销

【总结】

HashMap 采用 2 的 n 次方倍扩容是一个经过精心设计的工程优化，它：

利用位运算大幅提升索引计算速度
保证哈希分布的均匀性
优化扩容时的元素迁移效率
完全契合计算机的二进制特性

这种设计体现了 Java 集合框架在理论数学（哈希分布）和工程实践（性能优化）之间的完美平衡。

# 为什么 HashMap 在 Java 中扩容时采用 2 的 n 次方倍？