Dlaczego HashMap wymaga, aby początkowa pojemność była potęgą dwóch?

Question

szedłem kodu źródłowego HashMap Java kiedy zobaczyłem następującą

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

Moje pytanie brzmi, dlaczego ten wymóg istnieje w pierwszej kolejności? Widzę również, że konstruktor, który pozwala na tworzenie HashMap o pojemności niestandardowego zamienia go na mocy dwóch:

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

Dlaczego pojemność zawsze musi być potęgą dwójki?

Co się dzieje, gdy wykonywane jest automatyczne ponowne zacieranie? Czy funkcja skrótu jest również zmieniona?

Answer 1

Mapa musi ustalić, który indeks tabeli wewnętrznej ma być użyty dla danego klucza, odwzorowując każdą wartość int (może być ujemną) na wartość z zakresu [0, table.length). Kiedy table.length jest potęgą dwójki, co można zrobić naprawdę tanio - i jest w indexFor:

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

Z innej długości stołu, to trzeba obliczyć resztę i upewnić się, że nie- negatywny . Jest to zdecydowanie mikro-optymalizacja, ale prawdopodobnie poprawna :)

Co się dzieje, gdy wykonywane jest automatyczne ponowne zacieranie? Czy funkcja skrótu jest również zmieniona?

Nie jest dla mnie jasne, co masz na myśli. Stosowane są te same kody skrótu (ponieważ są one obliczane tylko przez wywołanie hashCode dla każdego klucza), ale będą one dystrybuowane inaczej w tabeli ze względu na zmianę długości tabeli. Na przykład, gdy długość tablicy wynosi 16, kody skrótu 5 i 21, oba kończą się w zapisie w tabeli 5. Gdy długość tablicy wzrasta do 32, będą one w różnych wpisach.

Answer 2

Idealna sytuacja polega na użyciu liczb pierwszych w tablicy pomocniczej urządzenia HashMap. W ten sposób twoje klucze będą bardziej naturalnie rozłożone w całej tablicy. Działa to jednak z podziałem modów, a każda operacja Java staje się wolniejsza i wolniejsza. W pewnym sensie potęga 2 podejścia jest najgorszym rozmiarem tabeli, jaki można sobie wyobrazić, ponieważ przy słabej implementacji kodu hashowego istnieje większe prawdopodobieństwo wygenerowania kluczowych kolizji w macierzy.

Dzięki temu można znaleźć inną bardzo ważną metodę w implementacji Java HashMap, która jest hash(int), która kompensuje złe kody hash.