Java中HashSet首次插入耗时远高于二次插入的原因探究

这个问题其实直击HashMap（HashSet的底层实现）的核心扩容和冲突处理逻辑，结合你提到的Employee类用age生成hashCode()的细节，我来给你拆解清楚：

1. 首次插入的扩容开销是最大元凶 #

HashSet本质上是HashMap的“包装器”——它的add()方法就是调用HashMap的put()，把要插入的元素作为key，value是一个固定的PRESENT空对象。

HashMap默认初始容量只有16，负载因子是0.75。当元素数量达到容量 × 负载因子时，就会触发扩容：把容量翻倍，并且要重新计算所有已有元素的哈希位置（也就是rehash），再把它们迁移到新的数组桶位里。

你首次插入200万元素时，HashMap会经历N次扩容：从16→32→64→…直到容量足够容纳200万元素（按负载因子0.75算，最终容量得是2^22=4194304才够）。每一次扩容都要遍历已有元素、重新哈希、迁移，这是极其耗时的操作，占了首次插入大部分的时间。

而第二次插入时，HashMap的容量已经足够大，完全不会触发扩容，直接省去了这部分巨大的开销。

2. 重复元素的快速跳过逻辑 #

如果第二次插入的是已经存在于Set中的Employee对象（或者hashCode和equals都匹配的对象），那么HashMap的put()方法会先通过hashCode()找到对应桶位，再用equals()判断元素是否已存在——一旦发现存在，直接返回旧值，不会执行任何插入或结构修改操作。这一步的耗时只是哈希计算+桶位查找+equals判断，比实际插入元素快得多。

3. 你的Employee类设计放大了冲突开销 #

因为你用age作为hashCode()的唯一依据，假设age的取值范围很小（比如0-100），会出现极端严重的哈希冲突：所有age相同的Employee都会挤在同一个桶位里。当桶位的链表长度超过8时，HashMap还会把链表转换成红黑树来优化查找，但这个转换和后续的树结构维护（比如旋转平衡）都需要额外时间。

首次插入时，你不仅要处理扩容，还要不断维护这些冲突的链表/红黑树，进一步拉长了耗时。而第二次插入时，这些冲突结构已经存在，但因为元素重复，不会修改这些结构，自然没有这部分开销。

关于你提到的“标注错误” #

你说第三次输出标注为HashMap实际对应HashSet首次插入结果，这应该是测试代码里的变量名或注释写错了，但本质上HashSet的插入逻辑完全依赖底层HashMap，所以HashSet首次插入的耗时就是HashMap插入大量元素的耗时——两者的性能表现是完全一致的，毕竟HashSet只是HashMap的一层薄包装。

内容的提问来源于stack exchange，提问作者shade0