HashMap에서 초기 용량이 2의 배수가되도록 요구하는 이유는 무엇입니까?

Question

나는 다음과 같은

//The default initial capacity - MUST be a power of two. 
static final int DEFAULT_INITIAL_CAPACITY = 16; 

내 질문을봤을 때 내가 자바의 HashMap의 소스 코드를 통해가는이 요구 사항은 처음부터 존재하는 않는 이유는?

이

int capacity = 1; 
while (capacity < initialCapacity) 
    capacity <<= 1; 

왜 항상이 용량이 2의 제곱이 될 않습니다 또한 사용자 정의 용량는 HashMap을 만들 수있는 생성자는 2의 거듭 제곱으로 변환 볼?

또한 자동 다시 해싱이 수행 될 때 정확히 어떻게됩니까? 해시 함수가 변경 되었습니까?

Answer 1

맵은 int 값 (음수 일 수 있음)을 [0, table.length) 범위의 값으로 매핑하여 주어진 키에 사용할 내부 테이블 인덱스를 찾아야합니다. table.length는 싸게 정말을 을 할 수있는 두 가지의 전원 인 경우 - indexFor에, 그리고 경우 : 다른 테이블의 길이와

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

, 당신은 나머지를 계산하고 있는지가 비의해야 할 것 부정. 이것은 분명히 마이크로 최적화이지만 아마도 유효한 것입니다.

또한 자동 재 심기가 수행 될 때 정확히 무엇이 발생합니까? 해시 함수가 변경 되었습니까?

당신이 의미하는 것이 분명하지 않습니다. 동일한 해시 코드가 사용됩니다 (각 키에 hashCode을 호출하여 계산되기 때문에).하지만 테이블 길이가 변경되어 테이블 내에서 다르게 분산됩니다. 예를 들어, 테이블 길이가 16 인 경우 5와 21의 해시 코드가 모두 테이블 항목 5에 저장됩니다. 테이블 길이가 32로 증가하면 서로 다른 항목에있게됩니다.

Answer 2

이상적인 상황은 실제로 HashMap의 뒷받침 배열에 소수 크기를 사용하는 것입니다. 그렇게하면 키가 배열 전체에 자연스럽게 분산됩니다. 그러나 이것은 mod division과 함께 작동하며 Java의 모든 릴리스에서 작업 속도가 느려지고 느려집니다. 어떤 의미에서 2 접근 방식의 힘은 상상할 수있는 최악의 테이블 크기입니다. 왜냐하면 열악한 해시 코드 구현으로 인해 배열에서 주요 충돌이 발생할 가능성이 높기 때문입니다.

이 때문에 Java의 HashMap 구현에서 또 다른 매우 중요한 메소드 인 hash(int)을 발견 할 수 있습니다.이 메소드는 열악한 해시 코드를 보완합니다.