HashSet 대 ArrayList의 contains () 성능

1. 소개

이 빠른 가이드에서는 java.util 에서 사용할 수 있는 contains () 메서드 의 성능에 대해 설명합니다 . HashSetjava.util. ArrayList . 둘 다 객체를 저장하고 조작하기위한 컬렉션입니다.

HashSet 은 고유 한 요소를 저장하기위한 컬렉션입니다. HashSet 에 대해 자세히 알아 보려면 이 링크를 확인하십시오.

ArrayListjava.util.List 인터페이스 의 인기있는 구현입니다 .

여기에 ArrayList 에 대한 확장 기사가 있습니다.

2. HashSet.contains ()

내부적으로 HashSet 구현은 HashMap 인스턴스를 기반으로 합니다. 포함 () 메소드 호출 HashMap.containsKey (객체) .

여기서는 객체 가 내부 맵에 있는지 여부를 확인합니다 . 내부 맵은 버킷이라고하는 노드 내부에 데이터를 저장합니다. 각 버킷은 hashCode () 메서드로 생성 된 해시 코드에 해당합니다 . 따라서 contains () 는 실제로 hashCode () 메서드를 사용 하여 객체의 위치 를 찾습니다 .

이제 조회 시간 복잡성을 결정 해 보겠습니다. 계속 진행하기 전에 Big-O 표기법에 익숙해야합니다.

평균적 으로 HashSetcontains ()O (1) 시간에 실행됩니다 . 얻기 객체의 버킷 위치하여 일정 시간 작업입니다. 가능한 충돌을 고려 하면 내부 버킷 구조가 TreeMap 이므로 조회 시간이 log (n) 까지 증가 할 수 있습니다 .

이것은 내부 버킷 구조에 LinkedList 를 사용한 Java 7의 개선 사항입니다 . 일반적으로 해시 코드 충돌은 거의 발생하지 않습니다. 따라서 요소 조회 복잡성을 O (1) 로 간주 할 수 있습니다 .

3. ArrayList.c ontains ()

내부적으로 ArrayListindexOf (object) 메서드를 사용하여 객체가 list에 있는지 확인합니다 . 같이 IndexOf (오브젝트) 메소드는 전체 어레이를 반복 처리로 각 요소를 비교하여 동등한 (객체) 방법.

복잡성 분석으로 돌아가서 ArrayList . contains () 메서드는 O (n) 시간이 필요합니다 . 따라서 여기서 특정 객체를 찾는 데 소요되는 시간은 배열에있는 항목의 수에 따라 다릅니다.

4. 벤치 마크 테스트

이제 성능 벤치 마크 테스트로 JVM을 워밍업 해 보겠습니다. JMH (Java Microbenchmark Harness) OpenJDK 제품을 사용할 것입니다. 설정 및 실행에 대해 자세히 알아 보려면 유용한 가이드를 확인하세요.

시작하려면 간단한 CollectionsBenchmark 클래스를 만들어 보겠습니다 .

@BenchmarkMode(Mode.AverageTime) @OutputTimeUnit(TimeUnit.NANOSECONDS) @Warmup(iterations = 5) public class CollectionsBenchmark { @State(Scope.Thread) public static class MyState { private Set employeeSet = new HashSet(); private List employeeList = new ArrayList(); private long iterations = 1000; private Employee employee = new Employee(100L, "Harry"); @Setup(Level.Trial) public void setUp() { for (long i = 0; i < iterations; i++) { employeeSet.add(new Employee(i, "John")); employeeList.add(new Employee(i, "John")); } employeeList.add(employee); employeeSet.add(employee); } } }

여기에서 Employee 개체 의 HashSetArrayList 를 만들고 초기화 합니다.

public class Employee { private Long id; private String name; // constructor and getter setters go here }

우리는 추가 직원 = 신입 사원 (100L, "해리") 두 컬렉션의 마지막 요소로 인스턴스를. 따라서 최악의 경우 직원 개체의 조회 시간을 테스트합니다 .

@OutputTimeUnit (TimeUnit.NANOSECONDS) 는 결과를 나노초 단위로 원한다는 것을 나타냅니다. 기본 @Warmup 반복 횟수는 우리의 경우 5입니다. @BenchmarkMode이 설정되어 Mode.AverageTime 우리는 평균 실행 시간을 계산에 관심이있는 것을 의미한다. 첫 번째 실행을 위해 컬렉션 에 반복 = 1000 개 항목을 넣습니다 .

그런 다음 벤치 마크 메서드를 CollectionsBenchmark 클래스에 추가합니다.

@Benchmark public boolean testArrayList(MyState state) { return state.employeeList.contains(state.employee); }

여기서 employeeListemployee 객체 가 포함되어 있는지 확인합니다 .

마찬가지로 employeeSet에 대한 친숙한 테스트가 있습니다 .

@Benchmark public boolean testHashSet(MyState state) { return state.employeeSet.contains(state.employee); }

마지막으로 테스트를 실행할 수 있습니다.

public static void main(String[] args) throws Exception { Options options = new OptionsBuilder() .include(CollectionsBenchmark.class.getSimpleName()) .forks(1).build(); new Runner(options).run(); }

결과는 다음과 같습니다.

Benchmark Mode Cnt Score Error Units CollectionsBenchmark.testArrayList avgt 20 4035.646 ± 598.541 ns/op CollectionsBenchmark.testHashSet avgt 20 9.456 ± 0.729 ns/op

우리는 명확하게 볼 수 있습니다 testArrayList의 방법이있다 4035.646 NS 반면, 평균 조회 점수를 testHashSet를 함께 수행 빠른 9.456 ns의 평균.

이제 테스트에서 요소 수를 늘리고 반복 = 10.000 항목에 대해 실행 해 보겠습니다.

Benchmark Mode Cnt Score Error Units CollectionsBenchmark.testArrayList avgt 20 57499.620 ± 11388.645 ns/op CollectionsBenchmark.testHashSet avgt 20 11.802 ± 1.164 ns/op

여기에 또한는 ()이 들어 있는 HashSet의이 오버 엄청난 성능 이점이있다 ArrayList를 .

5. 결론

이 빠른 글 은 HashSetArrayList 컬렉션 의 contains () 메서드 성능을 설명합니다 . JMH 벤치마킹의 도움으로 각 컬렉션 유형에 대한 contains () 성능을 제시 했습니다.

결론적으로, 우리가 배울 수있는 (가) 포함 () 메소드는 빠른 작동 HashSet의 에 비해 ArrayList를 .

평소처럼이 기사의 전체 코드는 GitHub 프로젝트에 있습니다.