Passare alla funzione di hash HashMap in Java 8

Question

in Java 8 java.util.HashMap ho notato un cambiamento from:

static int hash(int h) { 
    h ^= (h >>> 20)^(h >>> 12); 
    return h^(h >>> 7)^(h >>> 4); 

to:

static final int hash(Object key) { 
    int h; 
    return (key == null) ? 0 : (h = key.hashCode())^(h >>> 16); 

Risulta dal codice che la nuova funzione è un semplice XOR dei 16 bit inferiori con il 16 superiore che lascia invariati i 16 bit superiori, in contrapposizione a diversi cambiamenti nella precedente implementazione, e dai commenti che questo è meno efficace nell'assegnare i risultati delle funzioni hash con ah Elevato numero di collisioni in bit inferiori a diversi bucket, ma consente di risparmiare i cicli della CPU dovendo eseguire meno operazioni.

L'unica cosa che ho visto nelle note di rilascio era lo change dagli elenchi collegati agli alberi bilanciati per archiviare le chiavi collidenti (che pensavo avrebbero potuto cambiare il tempo necessario per calcolare un buon hash), ero specificamente interessato a vedere se ci fosse qualche impatto sulle prestazioni atteso da questo cambiamento sulle mappe hash di grandi dimensioni. C'è qualche informazione su questo cambiamento, o qualcuno con una migliore conoscenza delle funzioni di hash ha un'idea di quali potrebbero essere le implicazioni di questo cambiamento (se c'è, forse ho solo frainteso il codice) e se c'era bisogno di generare hash codici in un modo diverso per mantenere le prestazioni durante il passaggio a Java 8?

Answer 1

Come è stato notato: c'è un significativo miglioramento delle prestazioni in HashMap in Java 8 come descritto in JEP-180. In sostanza, se una catena di hash supera una certa dimensione, lo HashMap sostituirà (ove possibile) con un albero binario bilanciato. Ciò rende il comportamento "peggiore" di varie operazioni O(log N) anziché O(N).

Questo non spiega direttamente la modifica a hash. Tuttavia, vorrei ipotizzare che l'ottimizzazione in JEP-180 significa che il risultato di prestazioni dovuto a una funzione hash scarsamente distribuita è meno importante e che l'analisi costi-benefici per il metodo hash cambia; cioè la versione più complessa è meno vantaggiosa in media. (Ricordare che quando il metodo hashcode del tipo di chiave genera codici di alta qualità, la ginnastica nella versione complessa del metodo hash è una perdita di tempo.)

Ma questa è solo una teoria. La vera motivazione della modifica hash è probabilmente riservata a Oracle.

Answer 2

Quando ho eseguito diffences implementazione hash vedo differenza di tempo in secondi nano, come di seguito (non eccezionale, ma può avere qualche effetto quando la dimensione è enorme ~ 1 milione +) -

7473 ns - Java 7

3981 java NS-8

Se stiamo parlando chiavi su ben formate e hashmap di grandi dimensioni (~ milioni), ciò potrebbe avere un certo impatto e questo è a causa della logica semplificata.

Answer 3

Come documentazione Java dice che l'idea è di gestire la situazione in cui la vecchia implementazione dell'elenco collegato esegue O (n) invece di O (1). Ciò accade quando viene generato lo stesso codice hash per un ampio set di dati inseriti in HashMap.

Questo non è uno scenario normale. Per gestire una situazione che una volta che il numero di elementi in un bucket hash cresce oltre una certa soglia, quel bucket passerà dall'utilizzo di un elenco collegato di voci a un albero binario. Nel caso di elevate collisioni di hash, ciò migliorerà le prestazioni di ricerca da O (n) a O (log n) che è molto meglio e risolve il problema delle prestazioni.