# 问题

5. 为什么 HashMap 的初始容量必须是 2 的幂次方?

# 标准答案

HashMap 的初始容量必须是 2 的幂次方,以便利用 位运算优化哈希寻址,使 index = (n - 1) & hash 计算索引时高效且均匀分布,从而提高查询和存储效率。如果容量不是 2 的幂次方,HashMap 会自动调整为最接近的 2 的幂,避免哈希冲突增多、空间浪费以及扩容时的复杂计算。

# 答案解析

# 1. HashMap 索引计算的优化

在 HashMap 中,键值对存储在 数组(table) 中,索引位置通过 hash & (n - 1) 计算,其中 n 是数组的长度(必须是 2 的幂次方)。

为什么用 n - 1 进行 & 运算?

  • 假设 n = 16(2^4),则 n - 1 = 15,二进制表示为 0000 1111
  • hash & 15 相当于 仅保留 hash 的低 4 位,保证索引计算落在 [0, 15] 的范围内。
  • 由于 2 的幂次方特性,& 计算 等价于取模运算(hash % n),但 &% 更快,因为位运算比除法效率高。

示例代码:

int index = hash & (table.length - 1); // 等效于 hash % table.length
1

# 2. 如果 n 不是 2 的幂会发生什么?

如果 n 不是 2 的幂,比如 n = 10,则 n-1 = 9 (1001),二进制 & 运算后,索引计算无法均匀分布,可能导致哈希冲突严重。

示例(n = 10)

假设 hash 计算的低几位:
1010 1100  结果:1100 & 1001 = 1000  → 落在索引 8
0110 0011  结果:0011 & 1001 = 0001  → 落在索引 1
1
2
3

可以看到 某些索引(如 8、1)会比其他索引更容易被命中,导致哈希分布不均,冲突严重。

HashMap 的优化

  • initialCapacity 不是 2 的幂时,HashMap 自动调整 为最接近的 2 的幂。
  • 例如 new HashMap<>(10) 实际上会调整为 16

源码(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;
}
1
2
3
4
5
6
7
8
9

这个算法的作用是将 cap 向上取整到 最近的 2 的幂

# 3. 避免扩容时 rehash 计算复杂

HashMap 采用 等量扩容(容量翻倍),每次扩容后新索引计算方式变为 hash & (2n - 1),这样可以快速决定元素是否需要迁移到新位置,避免重新计算所有哈希值,提高扩容效率。

扩容优化(JDK 1.8)

  • rehash 过程中,如果 hash & n == 0,元素 保留原索引
  • 否则,元素 索引 = 旧索引 + n,只需 O(1) 计算,避免 hashCode 重新计算。

示例:

if ((e.hash & oldCap) == 0)
    newTable[i] = e; // 位置不变
else
    newTable[i + oldCap] = e; // 迁移到新位置
1
2
3
4

# 4. JDK 1.7 与 JDK 1.8 处理索引的不同

版本 计算索引方式 扩容后索引迁移优化 计算复杂度
JDK 1.7 hash % length(但用 & 代替) 需要重新计算 hashCode() O(n)
JDK 1.8 hash & (length - 1) 只判断 hash & n,无需重新计算 hashCode() O(1)

# 5. HashMap 的常见问题

常见误区

  1. 误认为 HashMap 支持任意容量

    • HashMap 仅支持 2 的幂次方容量,若传入 10,最终会调整为 16。
  2. 误以为 n % mn & (m - 1) 计算结果相同

    • 只有 m 是 2 的幂次方时,n & (m - 1) 才等价于 n % m,否则会导致哈希分布不均。
  3. 忽视扩容导致性能下降

    • 频繁 put() 但未指定初始容量,可能触发多次扩容,影响性能。
    • 解决方案:预估 key 数量,合理设置 initialCapacity

# 深入追问

🔹 为什么 hash & (n - 1)hash % n 更快?
🔹 为什么 tableSizeFor 使用位运算调整容量?
🔹 为什么扩容时 hash & oldCap == 0 可以确定索引?
🔹 HashMap 什么时候会触发扩容?

# 相关面试题

为什么 HashMap 采用 n - 1 计算索引,而不是 n
ConcurrentHashMap 是否必须使用 2 的幂?
如何避免 HashMap 扩容影响性能?