자바의 HashMap 구현 해시 문제

: http://www.docjar.com/html/api/java/util/HashMap.java.html 난 다음주의 :자바의 HashMap 구현 해시 문제

가

사용되는 내부 데이터 구조는 배열을하는 각 인덱스의 저장에 연결된 첫 번째 항목에 대한 참조 명부. 배열 인덱스는 키의 해시 코드를 기반으로하며 링크 된 목록은 특정 해시 코드의 버킷을 나타냅니다. 흥미로운 것은 indexFor (int h, int length) 메서드입니다. 주어진 키에 대해 배열의 어떤 버킷을 볼지를 결정합니다. 그러나 구현시 반환 값은 & (길이 - 1)입니다. 지정된 배열 인덱스와 일치하지 않는 불확실한 수의 해시 코드의 경우 메서드는 0을 반환합니다. 따라서 개체에 대해 구현 한 고유 한 해시 코드가 없더라도 배열의 0 양동이는 대부분 개체로 가득 차서 따라서 고유 한 해시 코드가 제공하는 것으로부터 이점을 얻지 못합니다. 즉, 빠른 데이터 액세스입니다.

내가 누락 된 항목이 있습니까?

크리스티안

출처

2012-10-05 cristian.petroaca

당신은 HashMap의 소스 코드에서 다음의 Javadoc 누락 :

는

/** 
* The table, resized as necessary. Length MUST Always be a power of two. 
*/ 
transient Entry<K,V>[] table;

이 table.length-1 항상 1의 일련된다는 것을 의미합니다.

출처

2012-10-05 14:30:04 ddimitrov

그래, 그게 다야. 감사합니다. –

이번에는 해시 테이블 클래스와 관련된 또 다른 질문이 있습니다. 이 구현에서 http://www.docjar.com/html/api/java/util/Hashtable.java.html 배열의 버킷 인덱스는 key.hashcode % array.length를 사용하여 계산됩니다. 여기서 array.length는 2의 거듭 제곱이 아닙니다. 우리는 길이가 11 인 intial 배열을 가지고 hashcode = 1 인 키를 먼저 삽입하고, 배열 인덱스는 1이 될 것이고, hashcode = 12와 함께 또 다른 키를 삽입 할 것이므로 배열 인덱스도 1이 될 것입니다. 이것은 다른 해시 코드를 가진 2 개의 키에 대한 객체가 동일한 버킷에 저장된다는 것을 의미합니까? –

올바른 초기 값 (즉, 15)을 지정하면 크기 조정 공식'oldCapacity * 2 + 1'이 올바르게 유지됩니다. 프라임 번호는 이러한 경우의 일반적인 권장 사항이며 합리적으로 잘 작동합니다. 당신이 진절머리 나는 초기 크기를 지정하면 크기가 더 커질 것이다. 결국 완벽한 것은 아닙니다. 데이터 구조가 없습니다. 효율성에 대한 관심이 많다면 http://labs.carrotsearch.com/hppc.html을 확인해보십시오. 원하는대로 할 수있는 충분한 로프를 제공합니다 :-) – ddimitrov

나는 당신이 그 문제가 무엇이라고 생각하는지 이해할 수 없다.

h & (length - 1)은 h % n을 계산하는 간단한 방법입니다. 여기에서 n은 2의 거듭 제곱입니다. 내 이해에서 왜 h % n이 0을 부 자연스럽게 내야하는지에 대한 이유는 없습니다.

출처

2012-10-05 14:29:55 parsifal

자바의 HashMap 구현 해시 문제

답변

관련 문제