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 벤치마크 테스트를 작성해 보겠습니다 .
첫 번째 경우에는 집합과 컬렉션을 초기화합니다. 여기서 집합에는 컬렉션보다 더 많은 요소가 있습니다. 두 번째 경우에는 집합보다 컬렉션에 더 많은 요소가 있는 집합과 컬렉션을 초기화합니다. 그리고 세 번째 경우에는 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/opHashSet 이 removeAll() 메소드에 인수로 전달되는 Collection 보다 적은 요소를 가질 때 HashSet.removeAll()이 매우 나쁜 성능을 낸다는 것을 알 수 있습니다 . 그러나 다른 컬렉션이 다시 HashSet 이면 성능이 좋습니다.
5. 결론
이 기사에서는 HashSet에서 removeAll() 의 성능을 보았습니다 . 집합이 컬렉션보다 적은 수의 요소를 포함하는 경우 removeAll() 의 성능은 컬렉션 의 contains() 메서드의 시간 복잡도에 따라 달라집니다 .
