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        }    }}

之后，咱们增加咱们的基准测试：

@Benchmarkpublic boolean given_SizeOfHashsetGreaterThanSizeOfCollection_whenRemoveAllFromHashSet_thenGoodPerformance(MyState state) {    return state.employeeSet1.removeAll(state.employeeList1);}@Benchmarkpublic boolean given_SizeOfHashsetSmallerThanSizeOfCollection_whenRemoveAllFromHashSet_thenBadPerformance(MyState state) {    return state.employeeSet2.removeAll(state.employeeList2);}@Benchmarkpublic boolean given_SizeOfHashsetSmallerThanSizeOfAnotherHashSet_whenRemoveAllFromHashSet_thenGoodPerformance(MyState state) {    return state.employeeSet3.removeAll(state.employeeSet4);}

后果如下：

Benchmark                                              Mode  Cnt            Score            Error  UnitsHashSetBenchmark.testHashSetSizeGreaterThanCollection  avgt   20      2700457.099 ±     475673.379  ns/opHashSetBenchmark.testHashSetSmallerThanCollection      avgt   20  31522676649.950 ± 3556834894.168  ns/opHashSetBenchmark.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...