HashSet은 HashMap을 기본 데이터 구조로 사용하여 온라인으로 읽었습니다.채워진 ArrayList를 사용하여 HashSet을 초기화하는 시간의 복잡성은 얼마나됩니까?
그리고 HashMap는 LinkedList 또는 tree의 목적되는 목록의 각 항목과의 내부 데이터 구조로 ArrayList 이용한다.
이런 식으로 HashSet을 초기화 할 때 시간 복잡도는 어떻게됩니까? O (1) 일 수 있습니까? 그렇지 않다면, 왜?
List<Integer> list = new ArrayList<>();
list.add(1);
list.add(3);
list.add(2);
list.add(6);
list.add(0);
HashSet<Integer> set = new HashSet<>(list);
HashMap는 내부 데이터 구조 등의 ArrayList는 사용하지 않는다.
HashMap은 프리미티브 배열로 구축 된 해시 테이블을 유지 관리하며 충돌을 처리하기 위해 연결된 목록 또는 트리의 하이브리드 전략을 사용합니다. source code for java.util.HashMap을 검토하면이 사실을 알 수 있습니다.
해시 테이블을 작성하려면 모든 항목에서 해시 함수를 호출하여 해시 위치를 결정해야하므로 최소 경계는 O (N)입니다. 최악의 경우는 병적으로 배포 된 키 (예 : 모든 키가 충돌)에 대한 것이며, O (N)보다 훨씬 나빠질 수 있습니다. Java 8 구현은 최악의 경우 연결 목록 대신 균형 트리로 저하되므로 최악의 런타임은 O (N log N)이됩니다. (선형 프로빙을 사용하는 이전 버전의 Java에서는 최악의 경우가 O (N ²) 였을 것입니다.
java8의 기본 구현은 프로빙을 사용하지 않으며, 작은 버킷 (최대 8 개 항목)에 대해 연결된 목록을 사용하고 더 큰 버킷에 대해서는 트리를 사용합니다. –
@ k5_ : 그렇습니다. Java 8 구현은 Java 7 이전보다 훨씬 정교합니다. 나는 내 대답을 업데이 트했습니다, 고마워. –
@ DanielPryden, 설명 주셔서 감사합니다. 소스 코드를 살펴 보겠습니다. –
List에는 n 개의 개체가 모두 포함되어 있거나 모두 고유하거나 혼합되어있을 수 있습니다.
HashSet 컬렉션의 속성에는 중복 된 개체가 들어 있지 않습니다.
따라서 시간 복잡도가 List을 통과하고 HashSet 각 개체가 O(n)
귀하의 제목이 될 것입니다 추가'HashMap' 말한다, 그러나 당신의 코드는'HashSet'를 초기화하는 방법을 보여줍니다. –
지적 해 주셔서 감사합니다. 나는 그 질문을 갱신했다. –