HashSet 작업을 O (n)으로 만들려면 어떻게해야합니까?

Question

HashSet 작업을 O (n)으로 만들려면 어떻게해야합니까?

표준 수집 작업에는 Add, Remove, Contains가 있지만 해시 기반 구현을 사용하므로이 작업은 O (1)입니다.

그러나 연산 O (n)은 언제입니까?

감사합니다.

Answer 1

O (n) 동작을 유발할 수있는 한 가지 병적 인 경우는 모든 요소가 동일한 해시 코드를 가질 때입니다.

Answer 2

해시 함수 (해시 생성 함수 자체)가 O (n) 복잡도의 해시 키를 생성하면 모든 연산이이 복잡성을 띄게됩니다.

Answer 3

NPE는 대부분 정확합니다.

그러나 키 유형이 Comparable 인 경우에는 Java 8에서 HashMap 및 HashSet이 개선되어 긴 해시 체인을 2 진 트리로 대체해야합니다. 이 모든 요소가 Comparable를 구현하지 않습니다 같은 해시 코드 및 키 타입 이있을 때 O(N) 작업의 병적 인 경우에만 발생한다는 것을 의미

(JEP-180 참조). 키 유형이 Comparable 인 경우 또는 HashSet의 최악의 경우의 복잡도는 O(logN)입니다.

Answer 4

클래스를 재정의하지 않고이 작업을 수행하는 간단한 방법은 동일한 해시 코드로 많은 키를 만드는 것입니다. 예 :

Set<Long> longs = new HashSet<>(); 
for (int i = 0; i < 10000; i++) { 
    Long element = ((long) i << 32) + (i & 0xFFFFFFFFL); 
    assert element.hashCode() == 0; 
    longs.add(element); 
}