자바 HashMap의 동작은하지 O (1) 마크에 달려있다

나는이 프로그램을 실행하면자바 HashMap의 동작은하지 O (1) 마크에 달려있다

public class MyHashMapOperationsDebug { 

    public static void main(String[] args) { 
     MyHashMap hashMap = new MyHashMap();//MyHashMap is replica of HashMap 
     for (int i=1;i<=11;i++) 
     hashMap.put(i, i+100); 
     } 
}

및 MyHashMap.java는이

void addEntry(int hash, K key, V value, int bucketIndex) { //replica of HashMap's addEntry method 

Entry<K,V> e = table[bucketIndex]; 
**System.out.println("bucketIndex : " + bucketIndex);** 
    table[bucketIndex] = new Entry<K,V>(hash, key, value, e); 
    if (size++ >= threshold) 
     resize(2 * table.length); 
}

출력 :

bucketIndex : 7 
bucketIndex : 14 
bucketIndex : 4 
bucketIndex : 13 
bucketIndex : 1 
bucketIndex : 8 
bucketIndex : 2 
bucketIndex : 11 
bucketIndex : 11 
bucketIndex : 2 
bucketIndex : 8

일부 키가 이동하는 이유 11 개의 키만 크기 16의 맵에 저장하더라도 동일한 버킷에? 예 : 질문 하나 아래 입력을 읽은 후 : 자바의 HashMap의 & 정수를 사용하는 위의 경우에 복잡 될 것입니다 무엇 인덱스 2에서 양동이, 11는 두 개의 키 각

EDIT 있습니다. 그것은 O (1)입니까?

출처

2013-07-07 Java Geek

해시 테이블은 점근 적으로 만 O (1)이며 최악의 경우 O (n) 일 수 있습니다. 병적 최악의 경우는 각 항목이지도의 동일한 색인으로 해시 된 것입니다. – Will

통계라고합니다. – Bohemian

사이드 노트 : 기능의 품질에 따라 크게 좌우됩니다. 정말로 중요하다면, 당신은 hashCode() 메소드를 오버라이드 할 필요가있을 것이다. – allprog

사전에 모든 키를 모른 채로 키가 균등하게 분배되는 것을 보장하는 알고리즘을 설계하는 것은 불가능하기 때문에. 그리고 사전에 모든 키를 알고있는 경우에도 두 개의 hashCode가 동일한 경우 항상 동일한 키가됩니다.

그렇다고해서 HashMap이 O (1)이 아님을 의미하지는 않습니다. 맵의 항목 수에 관계없이 모든 버킷에 2 개의 항목이 있다고 가정하더라도 맵의 항목 수에 의존하지 않는 모든 get 작업을 시간에 따라 실행합니다. O (1).

출처

2013-07-07 10:14:55

지도의 항목 수에 관계없이 항상 –

답장을 보내 주셔서 감사합니다. 예를 들어,지도에 100 개의 항목이 있고 90 개가 충돌하는 경우입니다. 그래서 나는 90 개의 요소 체인을 가질 것입니다. 작업을 계속 수행 할 수 있습니까 O (1). 왜냐하면 우리는이 목록을 최대 90 개의 요소까지 트래버스해야한다고 생각하기 때문입니다. – zerocool

이것은 잘못된 분산 알고리즘 (HashMap의 경우가 아님) 또는 잘못된 hashCode() 구현이있는 Key 클래스의지도의 예입니다. 예를 들어, hashCode()의 구현이'return 1;'인 경우 HashMap에 그러한 키를 저장하면 O (n)이됩니다. 그러나 이것은 HashMap이 아니라 Key 클래스의 문제입니다. hashCode를 잘 분배한다고 가정하면 HashMap은 O (1)이됩니다. –

예. 인덱스 2의 버켓, 그리고 11은 각각 2 개의 키를 가지고 있습니다 : hashCollision 때문입니다. HashMap은 모든 n 요소에 대해 해시 콜리 전이있는 경우 조회에서 O (n)의 성능을 제공 할 수 있습니다. Thats는 해시 알고리즘의 잘못된 디자인입니다.

사실 이러한 충돌을 피하기 위해 여분의 공간이 할당되어 있다고 말할 수 있습니다. 해싱 기술을 사용하면 충돌이 많지 않으므로 여분의 백텟이 분명히 필요합니다.

그러나 동시에, 충돌을 완전히 피할 수는 없습니다. 왜냐하면 각 버킷에 하나의 항목 만있을 정도로 해싱 기술을 사용하면 많은 공간이 필요하기 때문입니다. 따라서 실제로는 hashCollisions가 한계가 있습니다.

출처

2013-07-07 10:26:14 zerocool

o (1) 해시 함수를 설계하기 전에 키 배포를 미리 아는 것은 매우 어렵습니다. 키 분배를 알고 있더라도 키는 동일한 슬롯에 매핑 될 수 있습니다. 따라서로드 요소가 특정 비율로 이동하면 다시 해싱해야합니다. 지도 크기가 16이고 17 개의 키가 있다고 가정하면 충돌이 발생합니다. 그래서이 상황에서 잠재적 인 충돌을 제거하기 위해지도를 다시 칠하기위한 메커니즘이 필요합니다.

해시 맵에서 찾기 연산은 점근 적으로 O (1)이지만 GO (O)도 가능합니다.

출처

2013-07-07 10:26:54 Trying

위의 경우 HashMap & 정수의 Java가 사용되는 경우의 복잡도는 어떻게됩니까? 그것은 O (1)입니까?

예. Integer.hashcode() 메서드는 Integer 자체의 값을 반환하며 가능한 해시 값의 공간에 균일하게 분산됩니다.

따라서 해시 테이블의 성능이 최적화됩니다. 즉 get 작업에 대해서는 O(1)이고 put 작업에 대해서는 O(1) (상각)입니다.그리고 가능한 유일한 2^32 고유 키가 있기 때문에 우리는 그 점을 넘어서 어떻게 HashMap 배율 문제를 고려할 필요가 없습니다.

출처

2013-07-07 12:02:19

당신이 말했듯이> 2^32 고유 키가 가능합니다. 그래서 해시 맵의 최대 버킷 수는 2^32가 될 수 있으며 10 만 개 항목이 있더라도 –

자바 HashMap의 동작은하지 O (1) 마크에 달려있다

답변

관련 문제