HashMap 扩容机制：容量翻倍的代价

扩容的本质

HashMap 的数组不会自动变大，但也不会自动变小。当元素数量超过阈值时，需要扩容：

threshold = capacity × loadFactor = 16 × 0.75 = 12

当 size > 12 时 → 触发扩容

扩容做了什么？

旧数组（容量 16）          新数组（容量 32）
┌────┬────┬────┬────┐    ┌────┬────┬────┬────┬────┬────┐
│ 0  │ 1  │ 2  │ 3  │    │ 0  │ 1  │ 2  │ 3  │ 4  │ 5  │
└────┴────┴────┴────┘    └────┴────┴────┴────┴────┴────┘
      ↓ 容量翻倍              ↓ 重新分配所有元素

---

扩容的成本

扩容的代价是昂贵的：

1. 创建新数组（容量翻倍）
2. 重新计算所有元素的桶位置
3. 拷贝到新数组

对于 100 万元素的 HashMap，一次扩容需要重新处理 ~100 万元素。这是为什么预分配容量很重要。

---

扩容时机演示

import java.lang.reflect.*;

Map<String, Integer> map = new HashMap<>(2);

int capacity = getCapacity(map); // 2
int threshold = getThreshold(map); // 1（2 × 0.75 向下取整）

// 第一次添加：threshold = 1，立即扩容
map.put("a", 1); // 扩容！容量 2 → 4
// threshold 变为 3（4 × 0.75）

// 第二次添加：size = 2，threshold = 3，不扩容
map.put("b", 2); // 不扩容

// 第三次添加：size = 3，threshold = 3，触发扩容
map.put("c", 3); // 扩容！容量 4 → 8

---

扩容后的元素重分配

这是扩容最有趣的部分。元素不是简单地从 0 遍历到 n 重新分配，而是用了「高位分流」技巧：

旧容量 oldCap = 16 = 0b0001_0000
新容量 newCap = 32 = 0b0010_0000

对于每个元素，检查 hash & oldCap：
  hash & 16 == 0 → 新位置不变（原位置）
  hash & 16 != 0 → 新位置 = 原位置 + 16

示例：
  hash = 0b0001_1111 = 31    → 31 & 16 = 0   → 新位置 = 15（不变）
  hash = 0b0011_1111 = 63    → 63 & 16 = 16  → 新位置 = 15 + 16 = 31

这样平均只需要移动一半的元素，而不是全部重新分配。

---

链表在扩容时的拆分

JDK 1.8 使用尾插法，扩容时链表不会倒置：

扩容前 bucket[5] 链表：
a → b → c → d

JDK 1.7（头插法，扩容后可能倒置）：
d → c → b → a  ← 顺序反转了

JDK 1.8（尾插法，扩容后顺序不变）：
a → b → c → d  ← 顺序保持

这就是为什么 JDK 1.8 消除了并发扩容时的环形链表问题。

---

预分配容量的价值

性能对比

// 场景：添加 100 万元素
// 方式 1：默认容量（16）
Map<Integer, String> map1 = new HashMap<>();
// 扩容路径：16 → 32 → 64 → 128 → 256 → 512 → 1024 → 2048 → 4096 → 8192 → 16384 → 32768 → 65536 → 131072 → 262144 → 524288 → 1048576
// 共 17 次扩容，每次扩容都要重新分配元素
long start = System.nanoTime();
for (int i = 0; i < 1_000_000; i++) map1.put(i, "v");
System.out.printf("默认容量: %.0f ms%n", (System.nanoTime() - start) / 1_000_000.0);
// 典型输出：~400 ms

// 方式 2：预分配容量
Map<Integer, String> map2 = new HashMap<>(1_333_334); // 1000000 / 0.75 + 1
start = System.nanoTime();
for (int i = 0; i < 1_000_000; i++) map2.put(i, "v");
System.out.printf("预分配容量: %.0f ms%n", (System.nanoTime() - start) / 1_000_000.0);
// 典型输出：~120 ms
// 快了 3 倍以上

预分配容量的计算

// 如果你知道大概要存 1000 个元素：
int expectedSize = 1000;

// HashMap 内部会找第一个 >= expectedSize/0.75 的 2 的幂
// 1000 / 0.75 = 1333.33
// 第一个 >= 1333.33 的 2 的幂是 2048
Map<String, Object> map = new HashMap<>(expectedSize);
// 等价于 new HashMap<>(2048)

---

扩容的触发时机

触发条件	操作
size > threshold	扩容（容量翻倍）
数组为 null	初始化（容量 16）

HashMap 的扩容会一直进行到容量达到 MAXIMUM_CAPACITY (2^30)，之后不再扩容，但可以继续添加元素（直到 OOM）。

---

负载因子：时间和空间的权衡

负载因子	空间利用率	冲突概率	查找性能
0.5	50%	低	好
0.75（默认）	75%	中	平衡
0.9	90%	高	稍差

为什么 0.75 是默认值？这是经验和理论的平衡点：

负载因子太低的缺点：
  - 空间浪费严重（容量 16，实际只用 8 个位置）

负载因子太高的缺点：
  - 冲突增多，链表变长
  - 查找性能退化

0.75 是一个合理的折中：
  - 空间利用率 ≈ 75%
  - 平均链表长度 ≈ 1.5
  - O(1) 查找有保证

---

常见误区

误区 1：HashMap 不会自动缩小

Map<String, Integer> map = new HashMap<>();
for (int i = 0; i < 100000; i++) {
    map.put("key-" + i, i);
}
// 清空后，容量仍然是 131072（不会缩小）
map.clear();
System.out.println(getCapacity(map)); // 131072
// 如果确实需要缩小，只能重新创建：
map = new HashMap<>();

误区 2：一次性预分配太大

// ❌ 过度预分配
Map<String, Object> huge = new HashMap<>(1_000_000_000);
// 预分配了 10 亿容量的数组，内存开销巨大
// 如果实际只用了 1000 个元素，浪费严重

// ✅ 按需分配 + 合理预估
Map<String, Object> reasonable = new HashMap<>(10000);

误区 3：trimToSize() 没用

HashMap 确实没有 trimToSize() 方法。如果想释放多余容量，只能重新创建：

// 释放多余容量
Map<String, Integer> trimmed = new HashMap<>(map);
// 旧 map 可以等待 GC 回收

---

总结

要点	说明
扩容触发	size > capacity × loadFactor
扩容代价	创建新数组 + 重新分配所有元素
容量翻倍	16 → 32 → 64 → 128...
高位分流	hash & oldCap == 0 决定新位置，只需移动一半元素
JDK 1.8 改进	尾插法避免环形链表，链表不再倒置
预分配价值	大数据量下可提速 3 倍以上

一句话：扩容是 HashMap 的「性能税」，预分配是「逃税」的方法。

---

相关链接

• HashMap 底层实现
• HashMap 哈希冲突处理
• HashMap 性能调优