平均 86 纳秒的 put，为什么有一次要 21 毫秒
往默认容量的
HashMap里放 200 万个键，平均每次put86 纳秒，最慢的一次却要 21 毫秒，差了五个数量级。这一次正好是第 1,572,864 次put，表在这里扩容。换成new HashMap<>(2_000_000)也没用，扩容还是会发生，只有HashMap.newHashMap(2_000_000)才能消掉它。
ArrayList.add 和 HashMap.put 常被说成 O(1)。准确地说，它们的 O(1) 是均摊的：绝大多数操作很便宜，偶尔有一次要把整个底层数组复制一遍，这一次的代价摊到所有操作上，平均下来仍是常数。复杂度分析关心的是总量和平均，请求延迟看的却是每一次。那次 21 毫秒落在哪个请求上，那个请求就慢 21 毫秒。
本文用 JDK 21.0.5 测两件事：扩容的代价集中在哪几次操作上、预分配容量能不能消掉它；以及「元素少时顺序扫描比哈希查找快」这条经验在什么条件下成立。结果见文末配套实验。
一、均摊是把账摊平，每一笔并没有变小
OpenJDK 21 的 ArrayList 在数组满了时分配一个 1.5 倍大的新数组，把旧元素复制过去（空列表第一次先分配 10 个）。HashMap 在元素数超过「容量 × 负载因子 0.75」时把表扩大一倍，所有节点重新分桶。按这两条规则算：
| 加入元素 | 扩容次数 | 累计复制或搬移 | |
|---|---|---|---|
ArrayList，默认容量 | 1,000 万 | 36 | 2,769 万个引用，2.77 倍 N |
HashMap，默认容量 | 200 万 | 18 | 315 万个节点，1.57 倍 N |
累计代价是 N 的常数倍，这就是「均摊 O(1)」。ArrayList 的文档也只承诺这一点，增长策略的细节没有规定，1.5 倍是当前实现。但这笔账是按几何级数分布的：每次扩容复制的是当前全部元素，最后一次最大，前面所有次数加起来也只和它同一个量级。
实测逐次记录每个 add 和 put 的耗时。为了只看复制本身，这两组用不回收的 Epsilon GC 并预先触碰整个堆，排除 GC 和缺页。每种写法跑 3 轮，取第 3 轮：
| 均值 | p99 | 最大 | 最慢一次在第几次 | 超过 100 µs 的操作 | |
|---|---|---|---|---|---|
ArrayList，默认容量 | 26.0 ns | 42 ns | 2.41 ms | 9,230,100（扩容点） | 11 次 |
ArrayList，new ArrayList<>(n) | 24.3 ns | 42 ns | 0.05 ms | 不固定 | 0 次 |
HashMap，默认容量 | 86.0 ns | 250 ns | 21.27 ms | 1,572,864（rehash 点） | 8 次 |
HashMap，HashMap.newHashMap(n) | 78.0 ns | 209 ns | 0.44 ms | 0（见第三节） | 1 次 |
默认容量时，最慢的 10 次操作里，ArrayList 有 8 次落在扩容点上，HashMap 有 9 次落在 rehash 点上，剩下的是计时区间里的其他干扰。p99 完全看不出这些尖峰：200 万次操作里只有 8 次超过 100 微秒，占百万分之四。
两种结构的尖峰量级差了近十倍。把最后一次的耗时除以当时的元素数，ArrayList 约每个引用 0.26 纳秒，HashMap 约每个节点 13.5 纳秒。前者是一整块连续内存的复制；后者要逐个访问节点、按哈希值的一个比特位拆到两个桶里，是跟着指针跳的随机访存。所以同样的元素数，HashMap 的扩容贵得多。这两个单价只是这台机器上的推算，用来比较量级，不要当成常数。
二、尖峰在什么场景里会变成问题
预分配省下的总时间并不多：ArrayList 从 259.6 ms 降到 243.1 ms，HashMap 从 172.0 ms 降到 156.0 ms，都在一成左右。它真正改变的是最大值：ArrayList 从 2.41 ms 降到 0.05 ms，HashMap 从 21.27 ms 降到 0.44 ms。预分配主要是为了尾延迟，吞吐的收益是次要的。
尖峰要不要紧，看它落在谁身上：
- 一次请求里从空开始建一个大集合，比如导出报表时把 200 万行聚合进一个
HashMap：这个请求本来就要跑一两百毫秒，扩容已经算在总耗时里，尖峰只是其中一段，不会额外拖慢别的请求。 - 长期存活、在请求路径上持续增长的集合，比如进程内的本地索引、按 ID 缓存的会话表：哪个请求的写入碰上扩容，哪个请求就多等这一次复制的时间。集合越大，这一次越久，而且集合大到一定程度后，这种事一段时间才发生一次，很难从平均值或 p99 里看出来。
- 扩容发生在锁里：如果集合用
synchronized或Collections.synchronizedMap保护，扩容期间所有等这把锁的请求都跟着等。这是由机制推出的，本文没有单独测。ConcurrentHashMap的文档同样提醒，扩容可能比较慢，能预估大小时应在构造时给出。 - 实验排除了 GC：真实服务里，扩容还会分配一个新的大数组、留下一个旧的大数组，给 GC 增加压力。这部分的影响见 G1 与 ZGC。
所以尾延迟的来源不只是 GC 和网络。一个平均 O(1) 的操作，在它扩容的那一次里是 O(N) 的。
三、预分配：知道大小就告诉集合，但参数要看清
List<Order> list = new ArrayList<>(expected); // 参数是容量
Map<Long, Order> byId = HashMap.newHashMap(expected); // JDK 19+，参数是预期元素数
Map<Long, Order> wrong = new HashMap<>(expected); // 参数是表容量，放满之前仍会扩容
Map<Long, Order> shared = new ConcurrentHashMap<>(expected); // 参数是预期元素数同样是一个 int 参数，含义不一样：
| 写法 | 参数的含义 | 放入 200 万个键时 |
|---|---|---|
new HashMap<>(2_000_000) | 表的初始容量，向上取 2 的幂 | 表 2,097,152、阈值 1,572,864；放入第 1,572,865 个键时 rehash，实测 21.14 ms |
HashMap.newHashMap(2_000_000) | 预期元素数，按负载因子算好容量 | 不扩容，最慢一次 0.44 ms |
new ConcurrentHashMap<>(2_000_000) | 预期元素数 | 文档保证容纳这么多元素不需要扩容 |
new HashMap<>(n) 这一行最容易出错：它看上去已经预分配了，但只要 n 超过取整后容量的四分之三，最后还是要 rehash 一次，而且正好是最大的那一次。实测它的最大值和默认容量时一样，都在 21 毫秒左右。JDK 19 之后 HashMap(int) 的文档已经加了说明，要按预期元素数建表，应该用 newHashMap。JDK 19 之前的项目可以自己按 (int) Math.ceil(n / 0.75) 算容量，或者用 Guava 的 Maps.newHashMapWithExpectedSize。
预分配的 HashMap 最慢的一次出现在第 0 次 put：HashMap 的表是第一次放入时才分配的，构造时只记下容量。预分配没有让这 16 MB 的数组凭空消失，只是把分配挪到了第一个元素上，而且只有这一次。ArrayList(int) 则在构造时就分配数组。
不知道确切大小时，给一个偏大的估计也比不给好：多出来的只是一个空数组的内存，而少估了，最后一次扩容仍然会发生。已经创建好的 ArrayList 可以在批量加入前调用 ensureCapacity。
四、元素少时顺序扫描更快吗
另一条常听到的经验是：键只有几个的时候，遍历数组比 HashMap 快，不用算哈希。实测 N 从 1 到 256，比较在 String[] 里逐个 equals 和 HashMap.get。查询字符串和表里的键是不同的实例，哈希值已经预先算好（String 会缓存哈希值，被多次使用的键大多是这种情况），每个 N 取 7 次测量的中位数：
| N | 均匀查询：扫描 | 均匀查询：HashMap | 90% 命中热键：扫描 | 90% 命中热键：HashMap |
|---|---|---|---|---|
| 1 | 2.83 ns | 5.83 ns | 2.87 ns | 6.04 ns |
| 2 | 10.95 ns | 6.14 ns | 3.40 ns | 5.82 ns |
| 4 | 15.98 ns | 6.14 ns | 4.55 ns | 5.86 ns |
| 8 | 22.08 ns | 6.00 ns | 5.35 ns | 5.75 ns |
| 16 | 31.14 ns | 10.40 ns | 6.36 ns | 6.20 ns |
| 64 | 76.55 ns | 8.48 ns | 11.23 ns | 6.06 ns |
查询在所有键上均匀分布时，这条经验只在 N=1 时成立，N=2 时扫描就慢了近一倍。90% 的查询命中第一个键时，扫描一直领先到 N=8，到 N=16 才被追上。换成 int 键和 int[] 扫描，形状相同：N=1 时扫描 2.06 ns、HashMap 3.78 ns，N=2 起 HashMap 更快。
N 从 1 变成 2，扫描只多了半次比较，耗时却从 2.8 纳秒跳到 11 纳秒。多出来的主要不是比较本身，而是分支预测失败：命中位置是随机的，CPU 猜不到循环会在第几次退出，猜错一次就要丢掉已经推测执行的指令。热键分布下，循环几乎总在第一次就退出，分支很好猜，扫描的优势才显现出来。这个解释是从两种分布的差别推断的，实验没有读 CPU 的分支计数器。
所以交叉点不是一个固定的 N，它取决于查询分布、键的比较成本和 CPU。不要因为「只有十几个元素」就把 HashMap 手工改成数组扫描；真要改，用线上的真实查询分布测一次。多数时候差别只有几纳秒，只有在调用量极大的热点路径上才值得考虑。
五、测这类问题时要注意的几点
这组实验没有用 JMH，是为了拿到每一次操作的耗时，而不只是平均值。自己写计时代码时，以下几点决定了结果能不能信：
- 计时分辨率：这台机器上
System.nanoTime()的步长约 41 纳秒，单次操作的 p50 只能显示 0 或 41 ns。所以均值用总耗时除以次数得出，单次计时只用来找毫秒级的尖峰。 - 先预热：每种写法跑 3 轮只取最后一轮，查找实验整组先跑一遍再测，避开解释执行和 JIT 编译的阶段。JIT 对测量的影响见 JIT 与逃逸分析，微基准的通用做法仍是 JMH。
- 把要看的机制隔离出来：测扩容时用 Epsilon GC 和预触内存，否则 GC 停顿和缺页会混进结果。反过来，评估线上影响时要用真实的 GC 和负载，隔离环境里的数字不能直接搬过去。
- 看分布，不只看平均：均值和 p99 都看不出 200 万次里只出现几次的尖峰。要看最大值、看最慢的几次发生在哪里，线上则看高分位和最大值的监控，分位数的用法见 从「能跑」到「可观测」。
- 只信相对关系：尖峰的绝对值在多次运行间波动明显，
ArrayList最后一次扩容见过 2.4 到 10 毫秒。可以稳定复现的是：最慢的几次落在扩容点，预分配后最大值降一到两个数量级。
六、怎么用
- 能预估大小的集合都给出大小：
new ArrayList<>(n)、HashMap.newHashMap(n)、HashSet.newHashSet(n)、new ConcurrentHashMap<>(n)；不要用new HashMap<>(n)表达「预期 n 个元素」。 - 重点检查长期存活、在请求路径上增长的集合：本地索引、缓存、注册表。它们的扩容会落在某个用户请求上，集合越大，那一次越慢。
- 不要只凭元素少就把哈希查找改成扫描：交叉点取决于查询分布，均匀分布时 N=2 就已经不划算。
- 排查偶发的毫秒级慢请求时，除了 GC 和网络，也看看有没有大集合在这时扩容；应用内埋点记录最大值，而不只是均值。
- 复杂度仍然是第一位的：N=256 时扫描比
HashMap慢 20 倍，O(N) 与 O(1) 的差距在 N 变大后远超这些常数。常见的算法套路见 工程里用得上的十个算法套路。
配套实验
- codesphere-labs/system-design/amortized-cost-tail：
ArrayList扩容与HashMaprehash 的逐次耗时、三种HashMap构造方式的对照、两种查询分布下顺序扫描与哈希查找的交叉点（验证记录）
参考资料
- JDK 21 API：ArrayList（
add为均摊常数时间；增长策略的细节未作规定；ensureCapacity） - JDK 21 API：HashMap（超过负载因子与容量之积时 rehash，桶数约翻倍；
HashMap(int)的 API Note 与newHashMap） - JDK 21 API：ConcurrentHashMap（扩容可能较慢，建议构造时给出大小估计；构造参数为元素数）
- JDK 21 API：System.nanoTime