Java 集合类时间复杂度分析

最后修改:2025年4月22日

by baeldung

1. 概述

在本篇文章中，我们将深入分析 Java Collection API 中常用集合类的性能表现。当我们谈到集合类时，通常会想到 List、Map 和 Set 这三种数据结构，以及它们的常见实现类。

首先，我们会从 Big-O 复杂度的角度来分析常见操作的时间复杂度。随后，我们将通过实际的运行时数据来验证理论分析。

2. 时间复杂度

通常，当我们讨论时间复杂度时，指的是 Big-O 表示法。简单来说，它描述了算法运行时间随着输入规模增长的变化趋势。

如果你对 Big-O 表示法还不太熟悉，可以先阅读 Big-O 理论基础 和 Java 实例分析 的相关文章。

3. List

我们从最简单的有序集合 List 开始。

下面将分别介绍 ArrayList、LinkedList 和 CopyOnWriteArrayList 的性能表现。

3.1. ArrayList

Java 中的 ArrayList 是基于数组实现的。这有助于我们理解其内部逻辑。更详细的 ArrayList 实现细节可参考 这篇文章。

我们先从常见操作的时间复杂度入手：

  • add() – 平均时间复杂度为 *O(1)*，但最坏情况下（需要扩容并复制数组）为 O(n)
  • add(index, element) – 平均为 *O(n)*，因为可能需要移动后续元素
  • get() – 始终为常数时间 *O(1)*，直接通过索引访问
  • remove() – 时间复杂度为 *O(n)*，需要遍历数组查找目标元素
  • indexOf() – 同样为 *O(n)*，需要逐个比较元素
  • contains() – 基于 indexOf() 实现，因此也是 O(n)

3.2. CopyOnWriteArrayList

该集合类在多线程环境中非常有用。它线程安全，具体实现细节可参考 此文章。

CopyOnWriteArrayList 的性能表现如下：

  • add() – 取决于插入位置，平均为 O(n)
  • get() – 常数时间 O(1)
  • remove() – O(n)
  • contains() – O(n)

⚠️ 可以看出，该集合类的性能开销较大，特别是 add() 操作。

3.3. LinkedList

LinkedList 是一种线性结构，由节点组成，每个节点包含数据和指向下一个节点的引用。更多特性可参考 这篇文章。

常见操作的时间复杂度如下：

  • add() – 添加到末尾，仅需更新尾节点，O(1)
  • add(index, element) – 平均 *O(n)*，需要遍历到指定位置
  • get() – *O(n)*，需要从头遍历查找
  • remove(element) – 先查找再删除，O(n)
  • remove(index) – 从头遍历到指定位置后删除，O(n)
  • contains() – O(n)

3.4. JVM 预热

为了验证理论，我们使用实际数据进行测试。我们使用 JMH（Java Microbenchmark Harness）来测试集合类的常见操作性能。

如果你对 JMH 不熟悉，可以查看 这篇指南。

以下是我们的基准测试配置：

@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MICROSECONDS)
@Warmup(iterations = 10)
public class ArrayListBenchmark {
}

我们设置预热轮数为 10，并输出平均运行时间（单位：微秒）。

3.5. 基准测试

我们以 ArrayList 为例，编写测试代码：

@State(Scope.Thread)
public static class MyState {

    List<Employee> employeeList = new ArrayList<>();

    long iterations = 100000;

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

    int employeeIndex = -1;

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

        employeeList.add(employee);
        employeeIndex = employeeList.indexOf(employee);
    }
}

我们在 ArrayListBenchmark 中定义 State 类来初始化测试数据。

接着是具体测试方法：

@Benchmark
public void testAdd(ArrayListBenchmark.MyState state) {
    state.employeeList.add(new Employee(state.iterations + 1, "John"));
}

@Benchmark
public void testAddAt(ArrayListBenchmark.MyState state) {
    state.employeeList.add((int) (state.iterations), new Employee(state.iterations, "John"));
}

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

@Benchmark
public int testIndexOf(ArrayListBenchmark.MyState state) {
    return state.employeeList.indexOf(state.employee);
}

@Benchmark
public Employee testGet(ArrayListBenchmark.MyState state) {
    return state.employeeList.get(state.employeeIndex);
}

@Benchmark
public boolean testRemove(ArrayListBenchmark.MyState state) {
    return state.employeeList.remove(state.employee);
}

3.6. 测试结果

测试结果（单位：微秒）如下：

Benchmark                        Mode  Cnt     Score     Error
ArrayListBenchmark.testAdd       avgt   20     2.296 ±   0.007
ArrayListBenchmark.testAddAt     avgt   20   101.092 ±  14.145
ArrayListBenchmark.testContains  avgt   20   709.404 ±  64.331
ArrayListBenchmark.testGet       avgt   20     0.007 ±   0.001
ArrayListBenchmark.testIndexOf   avgt   20   717.158 ±  58.782
ArrayListBenchmark.testRemove    avgt   20   624.856 ±  51.101

✅ 从结果可以看出：

  • testContains() 和 testIndexOf() 性能相近
  • testAdd() 和 testGet() 差距巨大（2.296 vs 0.007）
  • 查找或删除元素大约需要 700 微秒，符合 O(n) 复杂度

同样，我们可以对 CopyOnWriteArrayList 进行测试，结果如下：

Benchmark                          Mode  Cnt    Score     Error
CopyOnWriteBenchmark.testAdd       avgt   20  652.189 ±  36.641
CopyOnWriteBenchmark.testAddAt     avgt   20  897.258 ±  35.363
CopyOnWriteBenchmark.testContains  avgt   20  537.098 ±  54.235
CopyOnWriteBenchmark.testGet       avgt   20    0.006 ±   0.001
CopyOnWriteBenchmark.testIndexOf   avgt   20  547.207 ±  48.904
CopyOnWriteBenchmark.testRemove    avgt   20  648.162 ± 138.379

✅ 从数据上看：

  • testGet() 仍为常数时间
  • testAdd() 比 ArrayList 慢得多，符合 O(n) 复杂度

最后是 LinkedList 的测试结果：

Benchmark        Cnt     Score       Error
testAdd          20     2.580        ± 0.003
testContains     20     1808.102     ± 68.155
testGet          20     1561.831     ± 70.876 
testRemove       20     0.006        ± 0.001

✅ 从中可以看出：

  • add() 和 remove() 性能很好
  • get() 和 contains() 性能较差，因为需要遍历链表

4. Map

在 JDK 最新版本中，Map 的实现性能得到了显著优化。例如，HashMap 和 LinkedHashMap 在冲突时使用平衡树代替链表，将最坏情况下的查找时间从 O(n) 降低到 *O(log n)*。

但如果你正确实现了 .equals() 和 .hashCode() 方法，冲突概率会大大降低。

关于 HashMap 冲突处理，可参考 这篇文章。*文中也提到，在理想情况下，HashMap* 的插入和查找操作为常数时间 O(1)。

4.1. 测试 O(1) 操作

我们先看 HashMap 的测试结果：

Benchmark                         Mode  Cnt  Score   Error
HashMapBenchmark.testContainsKey  avgt   20  0.009 ± 0.002
HashMapBenchmark.testGet          avgt   20  0.011 ± 0.001
HashMapBenchmark.testPut          avgt   20  0.019 ± 0.002
HashMapBenchmark.testRemove       avgt   20  0.010 ± 0.001

✅ 数据表明，上述方法的时间复杂度确实为 *O(1)*。

其他 Map 实现（LinkedHashMap、IdentityHashMap、WeakHashMap、EnumMap、ConcurrentHashMap）也具有类似表现：

Benchmark      LinkedHashMap  IdentityHashMap  WeakHashMap  ConcurrentHashMap
testContainsKey    0.008         0.009          0.014          0.011
testGet            0.011         0.109          0.019          0.012
testPut            0.020         0.013          0.020          0.031
testRemove         0.011         0.115          0.021          0.019

4.2. 测试 O(log(n)) 操作

对于基于树结构的 TreeMap 和 ConcurrentSkipListMap，其 put()、get()、remove() 和 containsKey() 的时间复杂度为 *O(log(n))*。

我们测试了不同规模数据下的运行时间：

items count (n)         1000      10,000     100,000   1,000,000
all tests total score   00:03:17  00:03:17   00:03:30  00:05:27

✅ 从结果可以看出，随着数据规模增加，运行时间呈对数增长，验证了 O(log(n)) 的复杂度。

5. Set

Set 是一个不包含重复元素的集合。我们将分析以下实现类：

  • HashSet
  • LinkedHashSet
  • EnumSet
  • TreeSet
  • CopyOnWriteArraySet
  • ConcurrentSkipListSet

HashSet 的内部实现依赖于 HashMap，因此其 add()、remove() 和 contains() 操作的时间复杂度为 *O(1)*。

**而 TreeSet 和 ConcurrentSkipListSet 由于基于树结构，时间复杂度为 O(log(n))。

CopyOnWriteArraySet 的操作复杂度为 *O(n)*。

5.1. 测试方法

@Benchmark
public boolean testAdd(SetBenchMark.MyState state) {
    return state.employeeSet.add(state.employee);
}

@Benchmark
public Boolean testContains(SetBenchMark.MyState state) {
    return state.employeeSet.contains(state.employee);
}

@Benchmark
public boolean testRemove(SetBenchMark.MyState state) {
    return state.employeeSet.remove(state.employee);
}

5.2. 结果对比

HashSet 的测试结果如下：

Benchmark      1000    10,000    100,000
.add()         0.026   0.023     0.024
.remove()      0.009   0.009     0.009
.contains()    0.009   0.009     0.010

LinkedHashSet 的结果：

Benchmark      1000    10,000    100,000
.add()         0.022   0.026     0.027
.remove()      0.008   0.012     0.009
.contains()    0.008   0.013     0.009

✅ 从结果可以看出，HashSet 和 LinkedHashSet 的操作时间基本一致，符合 O(1) 复杂度。

6. 总结

本文分析了 Java 中常用集合类的时间复杂度，并通过基准测试验证了理论分析。

我们通过 JMH 测试了各类集合的性能表现，并对比了不同集合在相同操作下的性能差异。最终，我们可以根据实际需求选择最适合的集合类。

完整代码可从 GitHub 获取。

原始标题:Time Complexity of Java Collections | Baeldung

« 上一篇： Java Weekly, 第245期
» 下一篇： Spring Security 集成测试指南