写点什么

Java 中 HashSet 的 removeAll 性能分析

用户头像
落日楼台H
关注
发布于: 2021 年 06 月 01 日
Java 中 HashSet 的 removeAll 性能分析

1. 概述

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


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

2. HashSet.removeAll()

该的 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 )。因此,从集合中删除 ArrayList 中存在的所有元素的总体时间复杂度为 O( n * m )


如果指定集合再次是 HashSet,则 contains()方法的时间复杂度为 O(1)。因此,从集合中删除 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-hashset-removeall-performance


发布于: 2021 年 06 月 01 日阅读数: 69
用户头像

落日楼台H

关注

还未添加个人签名 2019.03.05 加入

还未添加个人简介

评论

发布
暂无评论
Java 中 HashSet 的 removeAll 性能分析