HashMap 是 Java 中最常用的数据结构之一，其底层实现和扩容策略经过精心设计，兼顾了性能、内存使用和哈希分布。下面详细解释其底层结构以及为什么扩容是 2 倍（而不是 3 倍等）。
一、HashMap 的底层结构（以 Java 8+ 为例）
HashMap 底层是一个 “数组 + 链表/红黑树” 的混合结构：
- 主干：Node 数组 transient Node<K,V>[] table; 初始容量默认为 16。 每个 Node 是一个键值对（包含 hash, key, value, next）。
- 冲突处理：链表 or 红黑树 当多个 key 的哈希值映射到同一个数组下标（即“哈希冲突”），它们会以链表形式存储。 当链表长度 ≥ 8 且 数组长度 ≥ 64 时，链表会转为红黑树（提升查找性能，从 O(n) → O(log n)）。 如果红黑树节点数 ≤ 6，又会退化回链表。
- 哈希计算优化 实际索引 = (n - 1) & hash，其中 n 是数组长度。 这要求 n 必须是 2 的幂（见下文）。
二、为什么扩容是 2 倍？3 倍不行吗？
✅ 核心原因：为了高效重哈希（rehashing）
当 HashMap 扩容时，所有元素需要重新计算在新数组中的位置（因为数组长度变了）。如果新容量是 原容量的 2 倍（且保持 2 的幂），可以利用位运算快速确定新位置，而无需重新计算完整哈希值。
🔍 举个例子：
- 假设原容量
oldCap = 16（二进制10000） - 新容量
newCap = 32（二进制100000） - 某 key 的
hash = 25（二进制11001）
旧索引 = (16 - 1) & 25 = 15 & 25 = 01111 & 11001 = 01001 = 9
新索引 = (32 - 1) & 25 = 31 & 25 = 11111 & 11001 = 11001 = 25
但注意：新索引要么 = 旧索引，要么 = 旧索引 + oldCap
为什么？
因为 newCap = 2 * oldCap，所以新掩码比旧掩码多一位高位 1。
- 如果
hash在新增的那一位是0→ 新索引 = 旧索引 - 如果是
1→ 新索引 = 旧索引 + oldCap
✅ 这样，每个元素只需一次位判断，就能知道新位置，避免了昂贵的 % 或 hashCode() 重算。
❌ 如果用 3 倍（比如 16 → 48）会怎样？
- 容量不再是 2 的幂 → 无法使用
(n - 1) & hash快速取模。 - 扩容时无法快速 rehash：
- 哈希分布可能变差：
📌 Java 的 HashMap 依赖 hash 的低位随机性。通过 (n-1) & hash，只用低 log₂(n) 位决定位置。如果 n 是 2 的幂，这等价于取模，且效率最高。
三、为什么必须是 2 的幂？
| 容量 n | n-1（二进制） | 特点 |
|---|---|---|
| 16 | 1111 | 低位全 1，& 运算可截取 hash 低 4 位 |
| 32 | 11111 | 截取低 5 位 |
| 非 2 的幂（如 30） | 11110 | 低位有 0，导致某些 bit 位永远用不到 → 哈希聚集！ |
例如：若 n = 30，则 n-1 = 29 = 11101，那么 hash 的第 1 位（从 0 开始）永远被屏蔽为 0，导致一半的数组槽位永远无法被使用，严重浪费内存且加剧冲突。
四、总结
| 问题 | 答案 |
|---|---|
| 底层结构 | 数组 + 链表/红黑树 |
| 为什么扩容 2 倍？ | 1. 保持容量为 2 的幂 2. 支持 (n-1) & hash 高效取模3. 扩容时可快速 rehash（新位置 = 旧位置 或 旧位置 + oldCap） |
| 3 倍行不行？ | ❌ 不行： - 破坏 2 的幂性质 - 无法高效取模和 rehash - 可能导致哈希分布不均 |
| 其他语言呢？ | Python dict、Go map 也采用类似策略（容量为 2 的幂或质数，但 Java 选择 2 的幂以优化位运算） |
💡 所以，2 倍扩容不是随意定的，而是为了在 O(1) 时间内完成 rehash，并保证哈希均匀分布。这是时间和空间权衡下的最优解。