一个简单的去重优化：把 List.contains 换成 HashSet，性能差距可能非常大

不懂的浪漫

379人浏览 · 2026-04-21 09:34:55

不懂的浪漫 · 2026-04-21 09:34:55 发布

一个简单的去重优化：把 List.contains 换成 HashSet，性能差距可能非常大

在日常业务开发中，去重是一个非常常见的需求。

比如：

判断用户是否重复注册
判断订单是否已经处理过
判断文件是否已经上传过
判断某条数据是否已经存在
判断本次同步的数据是否需要入库

很多时候，我们第一反应可能是用 List 来保存已有数据，然后通过 contains() 判断元素是否存在。

例如：

List<String> existingMd5List = new ArrayList<>();

if (!existingMd5List.contains(fileMd5)) {
    // 不存在，执行插入逻辑
}

这种写法在数据量很小的时候没有什么问题，代码也很直观。

但是，一旦 List 集合的数据量变大，尤其是在循环或者嵌套循环中频繁调用 contains()，性能问题就会非常明显。

这篇文章就通过一个简单的例子，聊聊如何用 HashSet 或 HashMap 优化这种去重逻辑。
请添加图片描述

一个简单的去重场景

假设现在有两个集合。

一个集合表示数据库中已经存在的文件 MD5：

List<String> existingMd5List = Arrays.asList(
        "a1",
        "b2",
        "c3"
);

另一个集合表示本次新上传的文件 MD5：

List<String> uploadMd5List = Arrays.asList(
        "a1",
        "d4",
        "e5",
        "b2",
        "f6"
);

现在我们要做的事情很简单：

从 uploadMd5List 中找出数据库中不存在的 MD5。

也就是说，最终应该得到：

["d4", "e5", "f6"]

使用 List.contains 的写法

最直接的写法是：

List<String> newMd5List = new ArrayList<>();

for (String md5 : uploadMd5List) {
    if (!existingMd5List.contains(md5)) {
        newMd5List.add(md5);
    }
}

System.out.println(newMd5List);

输出结果：

[d4, e5, f6]

这段代码没有任何问题，而且很容易理解。

但是问题在于：

existingMd5List.contains(md5)

对于 ArrayList 来说，contains() 底层需要从第一个元素开始，一个一个往后比较。

如果集合中有 10 万个元素，最坏情况下可能要比较 10 万次，才能确定某个元素是否存在。

也就是说，List.contains() 的时间复杂度是：

O(n)

其中 n 是已有数据的数量。

如果外层还有一个循环，比如本次上传的文件数量是 m，那么整体复杂度就是：

O(m * n)

举个例子：

已存在的 MD5 数量：100,000
本次上传的 MD5 数量：10,000

如果每个上传文件都去 List 里查一遍，理论上可能产生接近：

100,000 * 10,000 = 1,000,000,000

也就是 10 亿次级别的比较。

这就是为什么有些代码在测试环境数据少的时候没问题，一到生产环境数据量上来，就突然变慢。

使用 HashSet 优化

如果我们的需求只是判断某个 MD5 是否已经存在，那么更合适的数据结构是 HashSet。

可以先把已有的 MD5 放到 HashSet 中：

Set<String> existingMd5Set = new HashSet<>(existingMd5List);

然后再判断：

List<String> newMd5List = new ArrayList<>();

for (String md5 : uploadMd5List) {
    if (!existingMd5Set.contains(md5)) {
        newMd5List.add(md5);
    }
}

System.out.println(newMd5List);

完整代码如下：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class DeduplicationDemo {

    public static void main(String[] args) {
        List<String> existingMd5List = Arrays.asList(
                "a1",
                "b2",
                "c3"
        );

        List<String> uploadMd5List = Arrays.asList(
                "a1",
                "d4",
                "e5",
                "b2",
                "f6"
        );

        Set<String> existingMd5Set = new HashSet<>(existingMd5List);

        List<String> newMd5List = new ArrayList<>();

        for (String md5 : uploadMd5List) {
            if (!existingMd5Set.contains(md5)) {
                newMd5List.add(md5);
            }
        }

        System.out.println(newMd5List);
    }
}

输出结果：

[d4, e5, f6]

代码逻辑和之前一样，都是找出不存在的 MD5。

但是查询效率不一样。

HashSet 底层基于哈希表实现，查找元素时会先计算元素的哈希值，然后根据哈希值快速定位到对应位置。

所以平均情况下，HashSet.contains() 的时间复杂度是：

O(1)

也就是说，不管集合里是 100 个元素，还是 10 万个元素，它的查询效率通常都比较稳定。

这样整体复杂度就从原来的：

O(m * n)

优化成了：

O(m)

严格来说，前面还有一步：

Set<String> existingMd5Set = new HashSet<>(existingMd5List);

这一步需要把 List 转成 HashSet，时间复杂度是：

O(n)

所以完整复杂度应该是：

O(n + m)

其中：

n 是已有 MD5 的数量
m 是本次上传 MD5 的数量

相比 O(m * n)，这个优化在大数据量场景下会明显很多。

HashSet 和 HashMap 应该怎么选？

这里很多人会有一个疑问：

既然 HashMap.containsKey() 也很快，那我到底应该用 HashSet，还是用 HashMap？

答案很简单。

如果你只是判断元素是否存在，用 HashSet。

如果你不仅要判断 key 是否存在，还要通过 key 获取对应的 value，用 HashMap。

HashSet 的适用场景

HashSet 只存元素本身，适合单纯的去重和存在性判断。

比如：

Set<String> md5Set = new HashSet<>();

md5Set.add("abc123");
md5Set.add("def456");

if (md5Set.contains("abc123")) {
    System.out.println("文件已经存在");
}

它表达的语义是：

这个元素有没有出现过？

适合这些场景：

判断文件 MD5 是否已经存在
判断用户名是否重复
判断手机号是否重复
判断订单号是否已经处理
批量导入时过滤重复数据

HashMap 的适用场景

HashMap 保存的是 key-value 映射关系。

比如：

Map<String, Long> md5FileIdMap = new HashMap<>();

md5FileIdMap.put("abc123", 1001L);
md5FileIdMap.put("def456", 1002L);

if (md5FileIdMap.containsKey("abc123")) {
    Long fileId = md5FileIdMap.get("abc123");
    System.out.println("文件已经存在，文件ID：" + fileId);
}

它表达的语义是：

这个 key 是否存在？如果存在，它对应的 value 是什么？

适合这些场景：

根据用户 ID 查用户对象
根据商品 ID 查商品价格
根据文件 MD5 查文件记录
根据订单号查订单状态
根据设备编码查设备信息

所以在本文这个文件 MD5 去重的场景中，如果只是判断 MD5 是否存在，使用 HashSet<String> 更合适。

如果后续还需要根据 MD5 获取数据库中的文件 ID、文件路径、文件对象等信息，那么使用 HashMap<String, FileInfo> 或 HashMap<String, Long> 更合适。

时间复杂度对比

我们可以简单对比一下。

数据结构	判断方式	单次查找复杂度	整体复杂度
`List`	`list.contains(value)`	`O(n)`	`O(m * n)`
`HashSet`	`set.contains(value)`	平均 `O(1)`	`O(n + m)`
`HashMap`	`map.containsKey(key)`	平均 `O(1)`	`O(n + m)`

其中：

n 表示已有数据量
m 表示本次需要处理的数据量

从这个对比可以看出，当数据量很小的时候，三者差距不明显。

但是当 n 和 m 都比较大时，List.contains() 的性能会急剧下降，而 HashSet 和 HashMap 的查询效率会稳定很多。

空间复杂度分析

使用 List 保存已有 MD5：

空间复杂度：O(n)

使用 HashSet 保存已有 MD5：

空间复杂度：O(n)

使用 HashMap 保存已有 MD5：

空间复杂度：O(n)

从大 O 表示法来看，它们的空间复杂度都是 O(n)。

但是需要注意，HashSet 和 HashMap 为了实现快速查找，底层会维护哈希表结构，所以实际内存占用通常会比 List 更高。

也就是说，这个优化的本质是：

用更多的内存，换取更快的查询速度。

在大多数业务系统中，尤其是批量处理、数据同步、去重导入这类场景，这个取舍通常是值得的。

进一步优化：处理本次上传数据中的重复

上面的代码只判断了：

上传的 MD5 是否已经存在于数据库中。

但是如果 uploadMd5List 本身也有重复数据呢？

比如：

List<String> uploadMd5List = Arrays.asList(
        "a1",
        "d4",
        "e5",
        "d4",
        "b2",
        "f6"
);

这里 "d4" 出现了两次。

如果我们希望最终结果中也不要重复，可以在加入结果集之后，把这个 MD5 也加入 Set：

List<String> newMd5List = new ArrayList<>();

for (String md5 : uploadMd5List) {
    if (!existingMd5Set.contains(md5)) {
        newMd5List.add(md5);
        existingMd5Set.add(md5);
    }
}

这样输出结果仍然是：

[d4, e5, f6]

因为第一次遇到 "d4" 时，它不在 existingMd5Set 中，所以会加入结果集。

随后执行：

existingMd5Set.add(md5);

第二次再遇到 "d4" 时，它已经在 existingMd5Set 中了，就不会重复加入结果集。

完整代码如下：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class DeduplicationDemo {

    public static void main(String[] args) {
        List<String> existingMd5List = Arrays.asList(
                "a1",
                "b2",
                "c3"
        );

        List<String> uploadMd5List = Arrays.asList(
                "a1",
                "d4",
                "e5",
                "d4",
                "b2",
                "f6"
        );

        Set<String> existingMd5Set = new HashSet<>(existingMd5List);

        List<String> newMd5List = new ArrayList<>();

        for (String md5 : uploadMd5List) {
            if (!existingMd5Set.contains(md5)) {
                newMd5List.add(md5);
                existingMd5Set.add(md5);
            }
        }

        System.out.println(newMd5List);
    }
}