왜 HashMap은 키 객체가 제공 한 해시 코드를 다시 해쉬합니까?

Question

내가 자바 1.6 API와 완벽하게 다음과 같은 작업의 필요성을 이해 할 수없는에서 제공하는 HashMap의 클래스의 코드를 읽고있다

(풋의 몸에서 발견 얻을 방법) :

int hash = hash(key.hashCode()); 

곳 방법을

private static int hash(int h) { 
     h ^= (h >>> 20)^(h >>> 12); 
    return h^(h >>> 7)^(h >>> 4); 
} 

이 효과적으로 공급 해시에 비트 연산을 실행하여 해시를 다시 계산 : hash()는 다음 본체를 갖는다. 나는 다음과 같이 API가 그것을 주장에도 불구하고 그렇게 할 필요성을 이해 드릴 수 없습니다 :

이 달리 해시 코드에 대한 충돌이 발생하는 것이 중요 의 HashMap가 전원의 - 두 개의 길이 해시 테이블을 사용하기 때문입니다 하위 비트가 과 다르지 않습니다.

키 값은 데이터 구조의 배열에 저장되며이 배열의 항목 색인 위치는 해시에 의해 결정된다는 것을 알고 있습니다. 내가 이해하지 못하는 것은이 함수가 해시 분포에 어떤 값을 추가 할 것인가입니다.

Answer 1

헬퍼가 작성한 것처럼 키 객체의 기존 해시 함수에 결함이 있으며 하위 비트를 혼합하는 데 충분하지 않습니다. the source 따르면

/** 
    * Returns index for hash code h. 
    */ 
static int indexFor(int h, int length) { 
    return h & (length-1); 
} 

해시가 (따라서 length-1가 1의 순서로 보장한다)을 2 제곱 길이의 AND 연산되고, pgras 인용. 이 ANDing으로 인해 하위 비트 인 h 만 사용됩니다. h의 나머지는 무시됩니다. 어떤 이유로 든 원래 해시가 2로 나눌 수있는 숫자 만 반환한다고 가정 해보십시오. 직접 사용한 경우 해시 맵의 홀수 위치는 절대 사용되지 않으므로 충돌 횟수가 2 배 증가합니다. 진정으로 병적 인 경우 나쁜 해시 함수는 해시 맵이 O (1) 컨테이너보다 목록처럼 동작하도록 만들 수 있습니다.

Sun 엔지니어는 너무 많은 해시 함수가 하위 비트에서 충분히 무작위 적이 아니며 많은 해시 맵이 상위 비트를 사용할만큼 크지 않다는 테스트를 실행해야합니다. 이러한 상황에서 HashMap의 비트 연산 인 hash(int h)은 추가 계산이 필요하지만 대부분의 예상 된 유스 케이스 (충돌 속도가 낮기 때문에)에 비해 실질적인 향상을 제공 할 수 있습니다.

Answer 2

어딘가에 당신의 hashCode 구현, 우물, 실수, 빠는 경우에도 좋은 배포를 보장하기 위해 읽었습니다.

Answer 3

해시 맵에서 알 수 있듯이 기본 구현은 해시 테이블, 특히 닫힌 버킷 해시 테이블입니다. 로드 요소는 컬렉션의 개체 수/총 버킷 수를 결정합니다.

더 많은 요소를 계속 추가한다고 가정 해 보겠습니다. 그렇게 할 때마다 업데이트가 아니며 객체의 hashcode 메서드를 실행하고 모듈러스 연산자와 함께 버킷 수를 사용하여 객체가 들어갈 버킷을 결정합니다.

으로 n 컬렉션)/m (버킷 수)이 커지면 읽기 및 쓰기 성능이 악화됩니다.

해시 코드 알고리즘이 놀랍다 고 가정하면 성능은 여전히이 비교에 따라 다릅니다.

다시 해싱은 버킷 수를 변경하고 컬렉션 생성시와 동일한로드 요소를 유지하는데도 사용됩니다.

해시 구현의 주요 이점은 읽기 및 쓰기에 이상적인 O (1) 성능이라는 점입니다.

Answer 4

아시다시피 object.hashCode()는 사용자가 재정의 할 수 있으므로 실제로 구현이 잘못되면 하위 비트가 아닌 임의의 비트가 발생합니다. 그러면 버킷 일부가 군집 해 버리고 버킷이 가득 채워지는 경향이 있습니다.

해시에서 수행하려는 작업에 대한 시각적 인 맵을 만들었습니다. 그것은 해시 (int h) 메서드는 비트 수준 manuplation을 수행하여 임의의 숫자를 생성하여 결과 숫자가 더 무작위로 (따라서 더 균일하게 버킷으로) 분배되도록하는 것 같습니다.

 h1 = h1^h13^h21^h9^h6  
     h2 = h2^h14^h22^h10^h7 
     h3 = h3^h15^h23^h11^h8 
     h4 = h4^h16^h24^h12^h9 
     h5 = h5^h17^h25^h13^h10 

다음과 같이

각 비트는 다른 비트에 다시 매핑된다. . . .

까지 h12.

보시다시피, 각 비트는 너무 멀리 떨어져있을 것입니다. 그래서 그것은 거의 무작위 적이기 때문에 특정 양동이를 군집시키지 않을 것입니다. 희망이 도움이됩니다. 가득 차있는 시각이 필요한 경우 나에게 이메일을 보내십시오.