乐趣区

关于java:Java-中-HashSet-的-removeAll-性能分析

jiezi

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…

退出移动版