HashSet 与 ArrayList 的 contains() 性能对比

1. 引言

本文将深入探讨 Java 中 HashSet 和 ArrayList 集合类的 contains() 方法在性能上的差异。这两个类虽然都用于存储和操作对象，但底层结构和性能特征截然不同，在实际开发中选错可能直接导致性能踩坑。

✅ HashSet：基于哈希表实现，保证元素唯一性。底层依赖 HashMap，适合高频查找、去重场景。
✅ ArrayList：List 接口的经典实现，基于动态数组，支持随机访问，但查找效率较低。

如果你对这两个集合的基础用法还不熟悉，建议先查阅 Java HashSet 详解和 Java ArrayList 指南。

2. HashSet.contains() 的性能机制

HashSet 的核心是内部持有一个 HashMap 实例，contains() 方法本质上是调用 HashMap.containsKey(object)。

具体流程如下：

调用目标对象的 hashCode() 方法，计算哈希值
根据哈希值定位到对应的“桶”（bucket）
在桶内进行 equals() 比较，确认对象是否存在

✅ 时间复杂度分析：

平均情况：O(1) —— 哈希定位是常数时间操作
最坏情况：O(log n) —— 当哈希冲突严重时，JDK 8+ 的桶结构会从链表升级为红黑树（TreeMap 结构），此时查找退化为 O(log n)

⚠️ 注意：相比 Java 7 使用链表处理冲突，Java 8 的树化优化大幅降低了极端情况下的性能衰减。在正常场景下，可认为 HashSet.contains() 是接近 O(1) 的高效操作。

3. ArrayList.contains() 的性能机制

ArrayList.contains() 的实现非常“简单粗暴”：

内部调用 indexOf() 方法
从头到尾遍历整个数组
对每个元素调用 equals() 方法进行逐个比对

✅ 时间复杂度分析：

O(n) —— 查找耗时与集合大小线性相关
最坏情况：目标元素在末尾或不存在，必须遍历全部 n 个元素

这意味着，数据量越大，查找越慢，不适合高频查询场景。

4. 基准测试（Benchmark）

我们使用 JMH（Java Microbenchmark Harness）进行性能压测，真实对比两者表现。如果你还不熟悉 JMH，可以参考我们的 JMH 使用指南。

4.1 测试类定义

@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@Warmup(iterations = 5)
public class CollectionsBenchmark {

    @State(Scope.Thread)
    public static class MyState {
        private Set<Employee> employeeSet = new HashSet<>();
        private List<Employee> employeeList = new ArrayList<>();

        private long iterations = 1000;

        private Employee employee = new Employee(100L, "Harry");

        @Setup(Level.Trial)
        public void setUp() {
            for (long i = 0; i < iterations; i++) {
                employeeSet.add(new Employee(i, "John"));
                employeeList.add(new Employee(i, "John"));
            }

            employeeList.add(employee);
            employeeSet.add(employee);
        }
    }
}

4.2 Employee 类

public class Employee {
    private Long id;
    private String name;

    public Employee(Long id, String name) {
        this.id = id;
        this.name = name;
    }

    // getter 和 setter 省略
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Employee employee = (Employee) o;
        return id.equals(employee.id) && name.equals(employee.name);
    }

    @Override
    public int hashCode() {
        return id.hashCode();
    }
}

⚠️ 注意：equals() 和 hashCode() 必须正确重写，否则 HashSet 无法正常工作。

4.3 基准测试方法

@Benchmark
public boolean testArrayList(MyState state) {
    return state.employeeList.contains(state.employee);
}

@Benchmark
public boolean testHashSet(MyState state) {
    return state.employeeSet.contains(state.employee);
}

4.4 启动测试

public static void main(String[] args) throws Exception {
    Options options = new OptionsBuilder()
      .include(CollectionsBenchmark.class.getSimpleName())
      .forks(1).build();
    new Runner(options).run();
}

4.5 测试结果

当集合大小为 1,000 时：

Benchmark                           Mode  Cnt     Score     Error  Units
CollectionsBenchmark.testArrayList  avgt   20  4035.646 ± 598.541  ns/op
CollectionsBenchmark.testHashSet    avgt   20     9.456 ±   0.729  ns/op

ArrayList 平均耗时：4035.646 纳秒
HashSet 平均耗时：9.456 纳秒
性能差距：约 426 倍

当集合大小为 10,000 时：

Benchmark                           Mode  Cnt      Score       Error  Units
CollectionsBenchmark.testArrayList  avgt   20  57499.620 ± 11388.645  ns/op
CollectionsBenchmark.testHashSet    avgt   20     11.802 ±     1.164  ns/op

ArrayList 耗时增长明显，达到 57.5 微秒
HashSet 仅微增至 11.8 纳秒
性能差距进一步拉大

✅ 结论：HashSet.contains() 的性能优势在数据量增大时更加显著，而 ArrayList 的查找时间呈线性增长。

5. 总结

通过理论分析和 JMH 实测，我们可以明确以下结论：

特性	HashSet.contains()	ArrayList.contains()
时间复杂度	O(1) 平均，O(log n) 最坏	O(n)
底层机制	哈希定位 + equals 比较	全量遍历 + equals 比较
适用场景	高频查找、去重、存在性判断	小数据量、顺序访问为主

✅ 最佳实践建议：

如果你需要频繁调用 contains()，优先使用 HashSet
ArrayList 适合读多写少、按索引访问的场景
使用 HashSet 时务必正确重写 equals() 和 hashCode()

本文完整代码已托管至 GitHub：https://github.com/eugenp/tutorials/tree/master/core-java-modules/core-java-collections-3

Persistence

REST

Security