⭐ 题目日期：

美团 - 2025/4/25

📝 题解：

HashMap 选择扩容为原来的 2 倍（即容量翻倍），主要基于以下几个核心的设计考量和计算机底层运算特性：

1. 优化哈希计算（核心原因）：

   • HashMap 需要通过 hash 值（经过扰动函数处理后的 key.hashCode()）来确定键值对应该放入哪个桶（bucket）中。计算桶索引的标准方法是：index = hash % capacity（取模运算）。
   • 取模运算 % 在 CPU 上的开销相对较大。
   • 当容量 capacity 是 2 的幂次方（如 16, 32, 64）时，可以利用位运算 & 来高效地替代取模运算：index = hash & (capacity - 1)。
     • 原理：如果 capacity 是 2 的 n 次方，那么 capacity - 1 的二进制表示就是 n 个连续的 1（例如：16(10000) - 1 = 15(01111)）。hash & (capacity - 1) 的操作本质上就是保留 hash 值的低 n 位，其结果范围正好是 [0, capacity - 1]，这与 hash % capacity 的效果完全等价。
     • 位运算 & 的效率远高于取模运算 %。 这是选择 2 的幂次方作为容量的最根本原因。

2. 保证扩容后容量仍是 2 的幂次方：

   • 为了持续享受上述位运算替代取模运算带来的性能优势，HashMap 必须确保扩容后的新容量仍然是 2 的幂次方。
   • 选择扩容为原容量的 2 倍，是最直接、最自然的方式： 因为 2 * (2^n) 的结果 2^(n+1) 必然也是 2 的幂次方（例如：16 -> 32 -> 64 -> 128）。**
   • 其他扩容因子（如 1.5 倍）通常无法保证结果总是 2 的幂次方（例如 16 * 1.5 = 24，不是 2 的幂次方）。

3. 优化元素迁移（Rehashing）：

   • 当 HashMap 扩容时，需要将所有已存在的键值对重新计算哈希并放入新的桶数组中（这个过程称为 rehash）。
   • 当容量是 2 的幂次方时，扩容为 2 倍有一个非常巧妙的特性：一个元素在新数组中的位置只可能是以下两种情况之一：
     • 保持不变（newIndex = oldIndex）
     • 或者迁移到 oldIndex + oldCapacity 的位置。
   • 原因： 因为 newCapacity = 2 * oldCapacity，所以 newCapacity - 1 的二进制表示就是在 oldCapacity - 1 的二进制表示前面多了一个 1（例如：old=16(10000), old-1=15(01111); new=32(100000), new-1=31(011111)）。进行 hash & (newCapacity - 1) 计算时，关键的变化在于 hash 值中原来被 oldCapacity - 1 忽略的那一位（即 oldCapacity 对应位，第 n+1 位）现在被 newCapacity - 1 包含了。
     • 如果 hash 值的这一位是 0，那么 hash & (newCapacity - 1) 的结果的低 n 位与 hash & (oldCapacity - 1) 相同，即 newIndex = oldIndex。
     • 如果 hash 值的这一位是 1，那么 hash & (newCapacity - 1) 的结果就是 oldIndex + oldCapacity（因为 oldCapacity 的二进制表示就是第 n+1 位为 1，后面全是 0）。
   • 这个特性极大地简化了 rehash 过程： HashMap 在扩容时（如 JDK 1.8+），不需要为每个元素重新计算 hash & (newCapacity - 1)，而是可以直接利用这个规律。它遍历旧数组的每个桶，根据桶中元素 hash 值新增的那一位是 0 还是 1，将它们分配到两个新的子桶（loHead/loTail 和 hiHead/hiTail）中，然后将这两个链表（或树）直接挂接到新数组的 oldIndex 和 oldIndex + oldCapacity 位置。这显著提高了扩容时元素迁移的效率。

4. 减少哈希冲突：

   • 虽然 2 的幂次方在某些特定情况下（如 hash 低位规律性差）可能略微增加冲突概率（这也是为什么引入了扰动函数来打散高位），但总体上，翻倍扩容能更平均地将元素分散到新的、更大的桶空间中，从而降低单个桶的负载因子，减少哈希冲突和链表的长度（或在 JDK 8+ 中减少树化的可能性），提升查询、插入效率。选择其他非 2 的幂次方的扩容因子，其分布效果通常不如翻倍好预测和优化。

总结：

HashMap 选择扩容为 2 倍，核心驱动力是为了 维持容量始终为 2 的幂次方。这带来了两大关键优势：

1. 性能优化： 用极其高效的位运算 hash & (capacity - 1) 替代昂贵的取模运算 hash % capacity 来计算桶索引。
2. 优化扩容迁移： 利用 2^n 扩容到 2^(n+1) 的特性，元素在新数组中的位置只有两种可能（原地或原位置+旧容量），大大简化了 rehash 过程，提升了扩容效率。

因此，虽然 2 倍扩容可能不是空间利用率最高的策略（例如，1.5 倍扩容可能更平滑），但它通过充分利用计算机的位运算特性，为 HashMap 的整体性能（尤其是高频的 get 和 put 操作）带来了显著提升，是性能与设计简洁性之间一个非常经典且高效的权衡。