面试题：简述HashMap 的长度为什么是2的幂次方 ？

HashMap 的底层数组（table）的长度始终是 2 的幂次方（如 16、32、64 等），这是为了优化性能并简化哈希值的映射过程。以下是具体原因：

---

1. 高效的下标计算

• HashMap 通过 (n - 1) & hash 的方式将哈希值映射到数组下标，其中 n 是数组的长度，hash 是键的哈希值。
• 当 n 是 2 的幂次方时，n - 1 的二进制表示形式是全 1。例如，n = 16 时，n - 1 = 15，其二进制为 1111。
• 这样，(n - 1) & hash 等价于 hash % n，但位运算（&）的效率远高于取模运算（%），从而提高了性能。

---

2. 均匀分布

• 当 n 是 2 的幂次方时，(n - 1) & hash 的结果能够均匀分布在 [0, n-1] 范围内。
• 如果 n 不是 2 的幂次方，某些下标可能会被频繁使用，而其他下标可能很少被使用，导致数据分布不均匀，增加哈希冲突的概率。

---

3. 扩容时的优化

• HashMap 在扩容时，新数组的长度是原数组长度的 2 倍（仍然是 2 的幂次方）。
• 扩容时，原有的键值对需要重新分配到新的数组中。由于长度是 2 的幂次方，可以通过简单的位运算确定键值对在新数组中的位置：
  • 如果 (hash & oldCap) == 0，则键值对在新数组中的位置不变。
  • 否则，键值对在新数组中的位置为 原位置 + oldCap。
• 这种方式避免了重新计算哈希值，提高了扩容的效率。

---

4. 减少哈希冲突

• 当 n 是 2 的幂次方时，(n - 1) & hash 能够充分利用哈希值的所有位信息，减少哈希冲突的概率。
• 如果 n 不是 2 的幂次方，某些位信息可能会被忽略，导致冲突概率增加。

---

示例：

假设 n = 16（2^4），n - 1 = 15，其二进制为 1111。对于任意哈希值 hash，(n - 1) & hash 的结果只会保留 hash 的低 4 位，确保下标在 [0, 15] 范围内。

int n = 16; // 数组长度
int hash = 12345; // 哈希值
int index = (n - 1) & hash; // 计算下标

---

总结：

HashMap 的长度设计为 2 的幂次方，主要是为了：

1. 通过位运算高效计算下标，提升性能。
2. 确保数据均匀分布，减少哈希冲突。
3. 优化扩容时的键值对重新分配过程。
4. 充分利用哈希值的所有位信息，降低冲突概率。

这种设计是 HashMap 高效运行的重要基础。