基于本文回答

播面 播面

文图音视，全方位拆解八股文
0
评论
请从左侧选择一个分类

详细讲讲HashMap 为什么容量要求是 2 的幂次方？

知识点图片

在 Java 中，HashMap 的容量（Capacity）必须是 2 的幂次方（比如 16, 32, 64 等）。如果我们在初始化时传入一个不是 2 的幂次方的值（比如 10），HashMap 也会通过位运算将其向上调整为最近的 2 的幂次方（即 16）。

这种设计是极其精妙的，主要出于以下 三个核心原因：

1. 极致的计算效率：用位运算替代取模运算

当我们将一个键值对存入 HashMap 时，需要计算它在数组中的下标（索引）。
传统的计算方式是取模运算：index = hash % length。

但是，取模运算（除法）在 CPU 层面是非常消耗性能的指令。而位运算（与、或、异或）直接在硬件底层执行，速度极快。

数学上有一个极其巧妙的特性：
当且仅当 length 是 2 的幂次方时，hash % length 的结果等价于 hash & (length - 1)。

  • 举个例子：
    假设 length = 16（2 的 4 次方）。
    length - 1 = 15。
    15 的二进制是 0000 1111。
    假设一个 hash 值为 0101 0101。
    hash & (length - 1) 的计算过程：
    ```text
    0101 0101 (hash)
    & 0000 1111 (15)

    0000 0101 (结果为 5)
    plaintext 
    你会发现，`& 15` 的操作，本质上就是截取了 `hash` 值的最后 4 位。这和十进制中对 1000 取模就是保留最后 3 位是一个道理。这比除法取模快得多。

2. 保证空间均匀分布，减少哈希冲突

如果 length 不是 2 的幂次方，会发生什么灾难性的后果？

假设 length = 15（不是 2 的幂次方）。
那么 length - 1 = 14。
14 的二进制是 0000 1110。

现在我们用它来进行位与运算：hash & 14。

plaintext 
      XXXX XXXX (任意 hash)
    & 0000 1110 (14)
    ----------------
      0000 XXX0 (结果的最后一位永远是 0！)
    ```
发现问题了吗？ 因为 14 的最后一位是 0，导致任何 `hash` 值和它进行 `&` 运算后，结果的最后一位必然是 0（即必然是偶数）。
这意味着：
1. `HashMap` 数组中索引为奇数的位置（1, 3, 5, 7...）永远不会被存入数据！
2. 空间浪费了一半。
3. 所有的元素都挤在偶数索引上，哈希冲突的概率会急剧增加。

结论： 只有当 `length` 是 2 的幂次方时，`length - 1` 的二进制才是 `0000 1111` 这种全 1 的结构。全 1 的结构能保证 `hash` 值的每一位都能发挥作用，从而让计算出的索引均匀散布在数组中。

---

### 3. 扩容（Resize）时的极致优化

`HashMap` 在元素装满到一定程度（达到负载因子，默认 0.75）时，会进行扩容。扩容时，数组长度会翻倍（比如从 16 变成 32），这也是保持 2 的幂次方。

扩容后，所有的元素都需要重新计算索引位置（Rehash）。在 Java 8 中，由于 2 的幂次方的特性，这个过程被优化到了极致。

*   扩容前的容量： 16（`length - 1` 为 15，二进制 `0000 1111`）
*   扩容后的容量： 32（`length - 1` 为 31，二进制 `0001 1111`）

对比两个掩码：
*   15：`0000 1111`
*   31：`0001 1111`
它们唯一的区别，就是在第 5 位（也就是原来 capacity 的那个高位）多了一个 1。

这意味着，一个元素在扩容后的新索引，完全取决于它 `hash` 值对应那一位（新增的那个 1 的位置）是 0 还是 1：
*   如果那一位是 0： 新索引 = 原索引。
*   如果那一位是 1： 新索引 = 原索引 + 旧容量（oldCapacity）。

源码中的巧妙实现：
Java 8 扩容时，不需要重新算一遍 `hash & (newCap - 1)`，而是直接判断：
```java
if ((e.hash & oldCap) == 0) {
    // 留在原位置
} else {
    // 移动到：原位置 + oldCap
}

这样做不仅省去了重新计算 hash 的开销，而且由于 hash 值的高低位是随机的，原来挤在同一个桶里的元素，会被均匀地拆分成两波，一半留在原地，一半搬到新位置。

补充：为了配合 2 的幂次方，HashMap 做的额外努力（扰动函数）

既然计算索引时 hash & (length - 1) 只用到了 hash 值的低位（比如 length=16 时，只用了最后 4 位）。那如果很多对象的 hash 值低位相同，高位不同，岂不是依然会发生严重的冲突？

是的。为了弥补这个由 2的幂次方 带来的副产物，HashMap 在获取 key.hashCode() 后，并没有直接使用，而是加上了扰动函数（Perturbation Function）：

java 
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

这段代码将 hashCode 的高 16 位向右移动，并与低 16 位进行异或运算（^）。
这样做的目的是让高位的特征也混合到低位中。哪怕最后只截取低位，低位里也包含了高位的信息，从而大大降低了哈希冲突的概率。

总结

HashMap 容量必须是 2 的幂次方，是追求极致性能的体现：

  1. 提速：用 & 运算代替 % 运算，计算索引极快。
  2. 防撞：保证 length - 1 的二进制全为 1，确保元素均匀分布，减少哈希冲突。
  3. 高效扩容：利用二进制特性，扩容时只需检查一位，即可快速完成数据迁移。
00:00
00:00