java.util.hash의 해시 코드 값을 계산할 때 사용되는 상수에 대한 설명

Question

누군가이 상수의 중요성과 그 이유를 설명 할 수 있습니까?

static int hash(int h) { 
     // This function ensures that hashCodes that differ only by 
     // constant multiples at each bit position have a bounded 
     // number of collisions (approximately 8 at default load factor). 
     h ^= (h >>> 20)^(h >>> 12); 
     return h^(h >>> 7)^(h >>> 4); 
    } 

소스 : 나는 또한 "마법"번호에 대해 궁금해

Answer 1

자바 SE6 라이브러리. 내가 아는 한 은의 매직 넘버입니다.
홀수와 소수는 해싱에서 사용할 수있는 흥미로운 우선 순위를 가지고 있음이 입증되었습니다 (1 차/2 차 클러스터링 등은 피하십시오).
대부분의 수치는 통계적으로 우수한 배포판을 제공하는 것으로 입증 된 연구 및 테스트 이후에 나온 것으로 생각됩니다. 특히이 숫자는 내가 아무 생각하지만 난 인상이 그렇게 왜이 특정 번호

Answer 2

이 이해 이러한 자질을 제시하는 이유 어느 쪽도 구현이 몰라 (잘하면 내가 해제 방법입니다 경우에 저를 정정 할 수 여기에 동료들) 무엇을 사실 좋은 해쉬 함수를 만드는 것은 까다 롭습니다. 실제로 사용되는 많은 다른 함수들이 있고 약간 다른 목적을 위해서입니다. 다음과 같이

자바의 해시 테이블이 작동 :

1. 그들은 해시 코드를 생성하는 키 오브젝트를 부탁드립니다. hashCode() 메서드의 구현은 분명히 가변적 인 품질 (최악의 경우 상수 값을 반환 함) 일 가능성이 높으며 작업중인 특정 해시 테이블에 맞지 않을 것입니다.
2. 그런 다음 위 함수를 사용하여 비트를 조금 섞어서 상위 비트에있는 정보도 하위 비트로 이동합니다. 다음은 중요하기 때문에 ...
3. 해시 테이블 체인의 배열에 인덱스를 가져 오기 위해 해시 코드 (해시 테이블 배열 항목 수)를 사용합니다. 해시 테이블 배열은 2의 거듭 제곱에 해당하는 크기를 가질 수 있으므로 2 단계에서 비트를 혼합하는 것이 중요합니다. 따라서 비트가 버려지는 일이 없도록하는 것이 중요합니다.
4. 그런 다음 동일한 키를 사용하여 항목에 도달 할 때까지 체인을 통과합니다 (equals() 방법에 따름).

그림을 완성하기 위해 해시 테이블 배열의 항목 수가 일정하지 않습니다. 체인이 너무 길어지면 배열이 새로운 배열로 바뀌고 모든 것이 다시 해치게됩니다. 이는 상대적으로 빠르며 일반적인 사용 패턴 (예 : put()이 많이 뒤 따르고 get()이 많이 뒤 따르는)에 대해 좋은 성능 영향을 미칩니다. 사용

실제 상수는 상당히 임의적 (아마도 큰 Integer 및 String 값의 번호와 같은 것들을 포함하여 몇 가지 간단한 신체와 실험에 의해 선택된다) 그러나 그들의 목적은 아니다 : 대부분의 전체 가치 확산의 정보를 얻기 값의 하위 비트는 hashCode()의 출력에있는 정보가 가능한 한 잘 사용되도록합니다.

(비슷한 이름에도 불구하고 완전히 다른 구현 전략을 사용합니다. 전자는 충돌을 피하거나 줄이기 위해 키 공간에 대한 지식이 필요하며, 후자는 필요합니다. 정보는 단지 낮은 비트가 아닌 모든 방향으로 이동해야합니다.)