拨开荷叶行,寻梦已然成。仙女莲花里,翩翩白鹭情。
IMG-LOGO
主页 文章列表 HashSet中removeAll方法的性能

HashSet中removeAll方法的性能

白鹭 - 2021-11-24 358 0 0

1.概述

HashSet是用于存储唯一元素的集合。

在本教程中,我们将讨论java.util.HashSet类中removeAll()方法的性能。

2. HashSet.removeAll()

removeAll collection中包含的所有元素:

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.内部实施和时间复杂性

The removeAll()方法确定哪个较小(集合或集合)。这是通过在集合和集合上size()

如果集合的元素少于集合的元素,则它将以时间复杂度O( n )遍历指定的集合。它还检查元素是否存在于时间复杂度为O(1)的集合中。并且如果存在该元素,则使用集合的remove()方法将其从集合中删除,该方法的时间复杂度为O(1)。因此,总体时间复杂度为O( n

如果集合中的元素少于集合,则使用O( n )对该集合进行迭代。 contains()方法检查集合中是否存在每个元素。并且如果存在这样的元素,则将该元素从集合中移除。因此,这取决于contains()方法的时间复杂度。

现在,在这种情况下,如果集合是ArrayList contains()方法的时间复杂度为O( m )。因此,从集合中ArrayList存在的所有元素的总时间复杂度n * m

如果该集合再次为HashSet contains()方法的时间复杂度为O(1)。因此,从集合中HashSet存在的所有元素的总体时间复杂度n

4.表现

为了查看以上三种情况之间的性能差异,让我们编写一个简单的JMH基准测试。

对于第一种情况,我们将初始化集合和集合,集合中的元素比集合多。在第二种情况下,我们将初始化集合和集合,集合中的元素要多于集合。在第三种情况下,我们将初始化2套,其中第二套具有比第一套更多的元素:

@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()表现非常差,后者作为参数传递给removeAll()方法。但是,当另一个集合再次是HashSet ,则性能良好。

5.结论

在本文中,我们看到了HashSet removeAll()当集合中的元素少于集合时, removeAll()的性能取决于集合contains()方法的时间复杂度。

标签:

0 评论

发表评论

您的电子邮件地址不会被公开。 必填的字段已做标记 *