1. 概述
HashSet 是 Java 中用于存储唯一元素的集合类。
本文将深入探讨 java.util.HashSet 类中 removeAll() 方法的性能表现。
2. HashSet.removeAll() 方法
removeAll() 方法会从当前 HashSet 中移除所有在指定集合中存在的元素：
Set<Integer> set = new HashSet<Integer>();
set.add(1);
set.add(2);
set.add(3);
set.add(4);
Collection<Integer> collection = new ArrayList<Integer>();
collection.add(1);
collection.add(3);
set.removeAll(collection);
Integer[] actualElements = new Integer[set.size()];
Integer[] expectedElements = new Integer[] { 2, 4 };
assertArrayEquals(expectedElements, set.toArray(actualElements));
执行后，set 中的元素 1 和 3 将被移除，最终保留 2 和 4。
3. 内部实现及时间复杂度分析
removeAll() 在执行时会先判断当前 HashSet 和传入集合的大小关系，通过调用两者的 size() 方法实现。
✅ 如果传入的集合元素更少，则遍历该集合（时间复杂度 O(n)），并检查每个元素是否存在于 HashSet 中（O(1)），若存在则调用 remove() 方法移除（O(1)）。
整体时间复杂度：O(n)
❌ 如果当前 HashSet 元素更少，则遍历 HashSet（O(n)），然后对每个元素调用传入集合的 contains() 方法判断是否存在。
此时复杂度取决于传入集合的 contains() 实现：
- 若传入集合是
ArrayList，其contains()是 O(m)，整体复杂度为 **O(n * m)**，性能较差。 - 若传入集合也是
HashSet，其contains()是 O(1)，整体复杂度为 **O(n)**，性能良好。
⚠️ 所以，传入集合的类型对性能影响很大。
4. 性能测试
我们使用 JMH 编写基准测试，验证不同情况下的性能差异：
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@Warmup(iterations = 5)
public class HashSetBenchmark {
@State(Scope.Thread)
public static class MyState {
private Set<Employee> employeeSet1 = new HashSet<>();
private List<Employee> employeeList1 = new ArrayList<>();
private Set<Employee> employeeSet2 = new HashSet<>();
private List<Employee> employeeList2 = new ArrayList<>();
private Set<Employee> employeeSet3 = new HashSet<>();
private Set<Employee> employeeSet4 = new HashSet<>();
private long set1Size = 60000;
private long list1Size = 50000;
private long set2Size = 50000;
private long list2Size = 60000;
private long set3Size = 50000;
private long set4Size = 60000;
@Setup(Level.Trial)
public void setUp() {
// 初始化数据
}
}
}
测试方法如下：
@Benchmark
public boolean given_SizeOfHashsetGreaterThanSizeOfCollection_whenRemoveAllFromHashSet_thenGoodPerformance(MyState state) {
return state.employeeSet1.removeAll(state.employeeList1);
}
@Benchmark
public boolean given_SizeOfHashsetSmallerThanSizeOfCollection_whenRemoveAllFromHashSet_thenBadPerformance(MyState state) {
return state.employeeSet2.removeAll(state.employeeList2);
}
@Benchmark
public boolean given_SizeOfHashsetSmallerThanSizeOfAnotherHashSet_whenRemoveAllFromHashSet_thenGoodPerformance(MyState state) {
return state.employeeSet3.removeAll(state.employeeSet4);
}
测试结果：
Benchmark Mode Cnt Score Error Units
HashSetBenchmark.testHashSetSizeGreaterThanCollection avgt 20 2700457.099 ± 475673.379 ns/op
HashSetBenchmark.testHashSetSmallerThanCollection avgt 20 31522676649.950 ± 3556834894.168 ns/op
HashSetBenchmark.testHashSetSmallerThanOtherHashset avgt 20 2672757.784 ± 224505.866 ns/op
分析总结：
- ✅ 当
HashSet比传入集合大时，性能表现良好； - ❌ 当
HashSet更小时，若传入集合是List，性能极差（几乎慢了上万倍）； - ✅ 若传入集合也是
HashSet，即使较小，性能依旧优秀。
5. 总结
本文分析了 HashSet.removeAll() 方法的性能表现。关键结论如下：
- 方法内部会根据集合大小选择遍历策略；
- 性能瓶颈通常出现在传入集合的
contains()实现； - 若传入集合是
List，且HashSet较小时，性能极差； - 若传入集合是
HashSet，性能始终保持在 O(n) 水平。
建议在使用 removeAll() 时，尽量保证传入集合为 HashSet 或其他 contains() 为 O(1) 的集合类型，避免踩坑。
完整示例代码见 GitHub：https://github.com/eugenp/tutorials/tree/master/core-java-modules/core-java-collections-3