HashSet中removeAll方法的性能
- java
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()方法的時間複雜度。