为何ArrayList插入数据的速度比HashSet更快？

测试场景说明 #

插入10,000,000个随机字符串元素时，测得性能数据如下：

• ArrayList 耗时：2,245秒
• HashSet 耗时：6,401秒

测试核心代码：

for (int i = 0; i < 10_000_000; i++) { 
    collection.add(RandomStringGenerator.generateRandomString()); 
}

性能差异的核心原因 #

HashSet 的 add 方法性能低于 ArrayList，完全源于两者底层实现逻辑的本质差异：

• 底层存储结构的复杂度不同
  ArrayList 基于动态数组实现，无扩容需求时，插入操作就是直接在数组末尾完成赋值，时间复杂度为O(1)；即便触发扩容，也是批量复制数组的操作，分摊到单个元素的开销极小。
  而 HashSet 底层依赖 HashMap 实现，每次插入元素实际是往 HashMap 中存入一组键值对（元素本身作为 key，一个固定的空 Object 作为 value），这个过程比单纯的数组赋值复杂数倍。

• 哈希计算与去重逻辑的额外开销
  调用 HashSet.add() 时，必须先计算元素的哈希值（调用元素的 hashCode() 方法），再通过哈希值定位存储位置；如果出现哈希冲突，还要调用 equals() 方法比对元素，确保集合中不存在重复元素。这两步计算和比对都会消耗额外的 CPU 资源。而 ArrayList 没有去重逻辑，也不需要哈希计算，直接执行插入动作即可。

• 内存布局导致的缓存效率差异
  ArrayList 的元素存储在连续的内存空间中，CPU 缓存命中率更高；而 HashMap 的散列结构（链表/红黑树）让元素在内存中分散存储，缓存命中率低，进一步拉高了插入操作的内存访问开销。

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