共计 2898 个字符，预计需要花费 8 分钟才能阅读完成。
1. 概述
HashSet 是一个用于存储惟一元素的汇合。
在本文中，咱们将探讨 java.util.HashSet 类中 removeAll()办法 的性能。
2. HashSet.removeAll()
HashSet 的 removeAll 办法删除所有蕴含指定汇合的元素：
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));后果，原汇合里的元素 1 和 3 将被中删除。
3. 外部实现和工夫复杂度
removeAll()办法会先确定哪个汇合更小，汇合大小不同，执行逻辑不同。这是通过在原汇合和指定汇合上调用 size() 办法来实现的。
如果指定汇合的元素少于指定原的元素 ，则它以工夫复杂度 O(n) 迭代指定的汇合。它还查看元素是否存在于工夫复杂度为 O(1) 的汇合中。如果元素存在，则应用汇合的 remove()办法将其从原汇合中 删除，该办法的工夫复杂度为 O(1)。所以 总的工夫复杂度是 O(n)。
如果原汇合的元素少于指定汇合 ，则它应用 O(n) 迭代此原汇合。而后它通过调用其 contains()办法查看指定汇合中是否存在每个元素。如果存在这样的元素，则从原汇合中删除该元素。所以这取决于 contains()办法的工夫复杂度。
当初在这种状况下，如果指定汇合是一个 ArrayList，contains()办法的工夫复杂度是 O( m)。因而，从汇合 HashSet 中删除 ArrayList 中存在的所有元素的总体工夫复杂度为 O(n * m)。
如果指定汇合再次是 HashSet，则 contains()办法的工夫复杂度为 O(1)。因而，从汇合 HashSet 中删除 HashSet 中存在的所有元素的总体工夫复杂度为 O(n)。
4. 性能
为了查看以上 3 种状况的性能差别，咱们来编写一个简略的 JMH 基准测试。
对于第一种状况，咱们将初始化原汇合和指定汇合，其中原汇合中的元素多于指定汇合。在第二种状况下，指定汇合中的元素多于原汇合。在第三种状况下，第二个汇合的元素数量比第一个汇合多：
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@Warmup(iterations = 5)
public class HashSetBenchmark {@State(Scope.Thread)
public static class MyState {private Set employeeSet1 = new HashSet<>();
private List employeeList1 = new ArrayList<>();
private Set employeeSet2 = new HashSet<>();
private List 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() {// populating sets}
}
}之后，咱们增加咱们的基准测试：
@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 的元素少于 Collection 时，HashSet.removeAll() 的体现十分蹩脚，Collection 作为参数传递给 removeAll()办法。然而当另一个汇合再次是 HashSet 时，则性能很好。
5. 论断
在本文中，咱们看到了 HashSet 中 removeAll()的性能。当原汇合的元素少于汇合的元素时，removeAll()的性能取决于汇合的 contains()办法的工夫复杂度。
最初，本文的残缺代码可 在 GitHub 上找到。
参考：https://www.baeldung.com/java…
