HashSet的removeAll()方法性能何如?
1. 引言
HashSet是 Java 集合 Set 的一个实现类,Set 是一个接口,其实现类除 HashSet 之外,还有 TreeSet ,并继承了Collection,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()
方法来确定上述代码中的set和collection 哪个更小。
如果 collection
的元素少于 set
, 则遍历 collection, 遍历的时间复杂度为 O(n) ,同时检查遍历的元素是否存在 时间复杂度为 O(1)
的 set 中。如果元素存在,将调用 set 的 remove() 方法将其从 set 中移除,时间复杂度仍然为O(1)。所以总的时间复杂度仍然为O(n)。
如果 set
中的元素少于 collection
, 那就遍历set
, 遍历的时间复杂度为 O(n)。然后,通过调用 contains() 方法来检查 collection
中是否存在这个元素。如果存在这样一个元素,那么该元素就会从 set
中移除。所以时间复杂度取决于contains()方法的时间复杂度。
在本例中,如果collection
的实例是 ArrayList
,那么 contains()
方法的时间复杂度为O(m),所以从set
中移除 ArrayList
中所有元素的总时间复杂度是O(n*m)。
如果collection
实例仍然是 HashSet
,则 contains() 方法的时间复杂度为O(1)。所以从set
中移除HashSet
中所有元素的总时间复杂度是 O(n) 。
4. 性能
为了查看以上三种情况之间的性能差异,让我们编写一个简单的JMH基准测试。
对于第一种情况,我们将初始化 set
和 collection
,其中 set
中的元素多于 collection
中的元素。
在第二种情况下,我们同样将初始化 set
和 collection
,其中 collection
中的元素多于 set
中的元素。
在第三种情况下,我们将初始化两个 set
,其中第二个set
比第一个 set
拥有更多的元素:
@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,collection 作为参数传递给 removeAll() 方法时,HashSet.removeAll() 的性能表现很差。但是,当removeAll() 方法的参数为 HashSet 时,则性能表现良好。
5. 总结
在本文中,我们探讨了 HashSet 中 removeAll()
方法的性能。当 set 的元素少于 collection 时,removeAll() 的性能取决于 collection 的 contains() 方法的时间复杂度。