자바에서의 HashMap 구현. 버킷 인덱스 계산은 어떻게 작동합니까?

Question

자바에서 HashMap의 구현을보고 있는데 한 지점에서 멈추었습니다.
indexFor 함수는 어떻게 계산됩니까?

static int indexFor(int h, int length) { 
    return h & (length-1); 
} 

감사

Answer 1

그것은 해시을 계산 아니에요, 그것은 버킷을 계산합니다.

발현 h & (length-1)하여 h % length의 초고속 변이체 제작 h의 하위 순서 비트를 반환하는 비트 마스크처럼 length-1를 이용하여 비트 단위 ANDh 온한다.

Answer 2

항목 (키 - 값 쌍)이 저장 될 해시 맵의 버킷을 계산합니다. 버킷 ID는 hashvalue/buckets length입니다.

해시 맵은 버킷으로 구성됩니다. 개체는 버킷 ID를 기반으로 이러한 버킷에 배치됩니다.

개체의 수는 실제로 hash code/buckets length 값을 기반으로 동일한 버킷에 포함될 수 있습니다. 이를 '충돌'이라고합니다.

많은 개체가 동일한 버킷에 포함되면 검색 중에 equals() 메서드가 검색되어 명확성이 제거됩니다.

충돌 수는 간접적으로 버킷의 길이에 비례합니다.

Answer 3

해시 자체는 저장하려는 개체의 hashCode() 메서드로 계산됩니다.

여기서 볼 수있는 것은 해시 h을 기반으로 개체를 저장하는 "버킷"을 계산하는 것입니다. 이상적으로는 충돌을 회피하기 위해 도달 가능한 최대 값이 h 인 것과 동일한 수의 버킷을 사용하지만 너무 많은 메모리가 필요할 수 있습니다. 따라서 충돌 위험이있는 버킷 수는 일반적으로 적습니다.

h이 1000이지만, 기본 배열에 512 개의 버킷 만있는 경우 개체를 넣을 위치를 알아야합니다. 보통 mod의 작업은 h이면 충분하지만 너무 느립니다. 기본 배열 항상이 2^n 동일한 버킷의 수는 h & (length-1)의 아이디어를 사용할 수있는 썬의 엔지니어, 그것은 숫자 실질적으로 단지 n을 읽는 모든 1 's의 구성과 bitwise AND을 수행했다고 HashMap의 내부 속성을 감안할 때 해시의 최하위 비트 (h mod 2^n과 동일 함)는 보다 빠릅니다.

예 :

 hash h: 11 1110 1000 -- (1000 in decimal) 
    length l: 10 0000 0000 -- (512 in decimal) 
     (l-1): 01 1111 1111 -- (511 in decimal - it will always be all ONEs) 
h AND (l-1): 01 1110 1000 -- (488 in decimal which is a result of 1000 mod 512)