Wyjaśnienie metody HashMap # hash (int)

Question

Czy ktoś może mi wyjaśnić statyczną metodę HashMap # hash (int)?

Jakie jest uzasadnienie, aby wygenerować jednolicie rozproszone hashy?

/** 
* Applies a supplemental hash function to a given hashCode, which 
* defends against poor quality hash functions. This is critical 
* because HashMap uses power-of-two length hash tables, that 
* otherwise encounter collisions for hashCodes that do not differ 
* in lower bits. Note: Null keys always map to hash 0, thus index 0. 
*/ 
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); 
} 

Przykład ułatwi trawienie.

Wyjaśnienie Jestem świadomy operatorów, tabel prawdy i operacji bitowych. Po prostu nie mogę tak naprawdę rozszyfrować implementacji ani komentarza. A nawet rozumowanie za tym.

Answer 1

>>> jest logiczną prawy shift (bez logowania dodatek) (JLS 15.19 Shift Operators), a ^ jest wyłącznym-bitowe lub (JLS 15.22.1 Integer Bitwise Operators).

W związku z tym, dlaczego tak się dzieje, dokumentacja zawiera wskazówkę: HashMap wykorzystuje tabele o wartości dwóch długości i miesza się, ukrywając wyższe bity i pobierając tylko niższe bity ich kodu skrótu.

// HashMap.java -- edited for conciseness 
static int indexFor(int h, int length) { 
    return h & (length-1); 
} 

public V put(K key, V value) { 
    int hash = hash(key.hashCode()); 
    int index = indexFor(hash, table.length); 
    // ... 
} 

So hash() próby przynieść trafności do wyższych bitów, które w przeciwnym razie byłoby uzyskać zamaskowanych away (indexFor zasadzie odrzuca wyższe bity h i zajmuje tylko dolna k bity gdzie length == (1 << k)).

Porównaj to ze sposobem, w jaki Hashtable (który nie powinien mieć tabeli mocy o dwóch długościach) używa kodu skrótu klucza.

// Hashtable.java -- edited for conciseness 
public synchronized V get(Object key) { 
    int hash = key.hashCode(); 
    int index = (hash & 0x7FFFFFFF) % table.length; 
    // ... 
} 

Czyniąc droższe % operację (zamiast prostego bitów maskowania), wydajność Hashtable jest mniej wrażliwy na mieszania kodów z słaba dystrybucja w niższych bitów (zwłaszcza jeśli table.length jest liczbą pierwszą).

Answer 2

Nie wiem, jak wszystkie dzieła przesuwania, ale motywacja jest określone w komentarzach:

Sposób HashMap jest realizowany zależy funkcja hashCode są dostatecznie dobrze zrealizowane. W szczególności niższe bity wartości mieszania powinny być równomiernie rozłożone. Jeśli masz dużo kolizji na niższych bitach, HashMap nie będzie działał dobrze.

Ponieważ implementacja hashCode znajduje się poza kontrolą HashMap (każdy obiekt może implementować własny), dostarczają one dodatkowej funkcji mieszającej, która nieznacznie przesuwa kod hash obiektu, aby zapewnić, że niższe bity są rozdzielane bardziej losowo. Ponownie, nie mam pojęcia, jak to działa dokładnie (lub jak jest efektywny), ale zakładam, że to zależy od co najmniej równomiernie rozłożonych bitów (wydaje się, że łączy on wyższe bity w niższe bity).

To co robi to, aby zminimalizować kolizje (i tym samym poprawić wydajność) w obecności źle zaimplementowanych metod hashCode.