Spiegazione del metodo hash (int) HashMap #

Question

Qualcuno può spiegarmi il metodo statico HashMap # hash (int)?

Qual è la giustificazione dietro di esso per generare hash uniformemente distribuiti?

/** 
* 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); 
} 

Un esempio renderebbe più semplice la digestione.

Chiarimento Sono a conoscenza degli operatori, delle tabelle di verità e delle operazioni bit a bit. Non riesco proprio a decodificare realmente l'implementazione né il commento. O anche il ragionamento dietro di esso.

Answer 1

>>> è il passaggio logico destra (nessun segno-estensione) (JLS 15.19 Shift Operators), e ^ è il bit per bit OR esclusivo (JLS 15.22.1 Integer Bitwise Operators).

Per quanto riguarda il motivo per cui questo è fatto, la documentazione offre un suggerimento: HashMap utilizza due tabelle di lunghezza power-of-two e cancella le chiavi nascondendo i bit più alti e prendendo solo i bit più bassi del loro codice hash.

// 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); 
    // ... 
} 

Quindi hash() tentativi per portare rilevanza ai bit superiori, che altrimenti ottenere mascherati distanza (indexFor scarta fondamentalmente i bit superiori di h e prende solo i bit inferiori k dove length == (1 << k)).

Contrasto con il modo in cui Hashtable (che NON deve avere una tabella di lunghezza power-of-two) utilizza il codice hash di una chiave.

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

Facendo quanto più costoso % funzionamento (invece di semplice mascheramento di bit), la prestazione di Hashtable è meno sensibile alle hash codici con cattiva distribuzione nei bit inferiori (soprattutto se table.length è un numero primo).

Answer 2

io non so come tutte le opere di spostamento, ma la motivazione è disposto nei commenti:

Il modo in cui la HashMap viene implementato si basa sulla funzione hashCode sufficientemente ben implementato. In particolare, i bit più bassi del valore hash dovrebbero essere distribuiti in modo uniforme. Se si hanno molte collisioni sui bit più bassi, la HashMap non funzionerà correttamente.

Poiché l'implementazione di hashCode è al di fuori del controllo di HashMap (ogni oggetto può implementare il proprio), fornisce una funzione hash aggiuntiva che sposta l'hashCode dell'oggetto per un po 'per garantire che i bit inferiori siano distribuiti in modo casuale. Ancora una volta, non ho idea di come funzioni esattamente (o quanto sia efficace), ma presumo che dipenda almeno dal fatto che i bit più alti siano equamente distribuiti (sembra che i bit più alti si inseriscano nei bit più bassi).

Quindi, ciò che fa è provare a ridurre al minimo le collisioni (e quindi migliorare le prestazioni) in presenza di metodi hashCode mal implementati.