2015-10-16 2 views
6

In base a this blog entry, HashMap reinvia la propria implementazione di hashCode() (denominata hash()) su un codice hash già recuperato.Perché e in che modo HashMap ha la propria implementazione interna di hashCode() chiamata hash()?

Se la chiave non è nullo, allora, esso chiamerà hashfunction sull'oggetto chiave, vedere linea 4 in metodo sopra cioè key.hashCode(), quindi dopo key.hashCode() restituisce hashValue, riga 4 assomiglia

int hash = hash (hashValue)

e ora, si applica tornato hashValue nella propria funzione di hashing.

Ci si potrebbe chiedere perché stiamo nuovamente calcolando l'hashvalue usando hash (hashValue). La risposta è, difende dalle funzioni di hash> di scarsa qualità.

Può hashmap accuratamente codici hash Riassegna? HashMap può memorizzare oggetti, ma non ha accesso alla logica che assegna a hashCode i suoi oggetti. Ad esempio, hash() non potrebbe forse integrano la logica dietro la hashCode() attuazione seguente:

public class Employee { 
protected long employeeId; 
protected String firstName; 
protected String lastName; 

public int hashCode(){ 
    return (int) employeeId; 
} 

} 
+3

Eventuali duplicati di [intesa strana funzione Java hash] (http://stackoverflow.com/questions/9335169/understanding-strange-java-hash-function) – Nayuki

+1

@NayukiMinase Indovina la realizzazione di 'hash()' è cambiato nel tempo, poiché la versione 1.8.0_51 è diversa/più semplice (vedi la mia risposta). – Andreas

risposta

13

Il hash() deriva la "migliorato" codice hash dal codice hash reale, in modo uguale ingresso sarà sempre uguale uscita (da jdk1 .8.0_51):

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

quanto al motivo per il codice hash ha bisogno di miglioramento, leggere il javadoc del metodo:

Calcola key.hashCode() una d sparge (XOR) bit più alti di hash per abbassarli. Poiché la tabella usa il mascheramento di potenza di due, gli insiemi di hash che variano solo in bit al di sopra della maschera corrente si scontreranno sempre. (Tra gli esempi noti vi sono insiemi di chiavi Float contenenti numeri interi consecutivi in ​​tabelle ridotte.) Quindi applichiamo una trasformazione che diffonde l'impatto di bit più alti verso il basso. Esiste un compromesso tra velocità, utilità e qualità della diffusione dei bit. Poiché molti set comuni di hash sono già ragionevolmente distribuiti (quindi non trarre vantaggio dalla diffusione), e poiché usiamo alberi per gestire grandi serie di collisioni nei bin, abbiamo solo XOR alcuni bit spostati nel modo più economico possibile per ridurre la perdita sistematica, nonché per incorporare l'impatto dei bit più alti che altrimenti non sarebbero mai utilizzati nei calcoli dell'indice a causa dei limiti di tabella.

+2

Per dirlo in un altro modo, la classe 'HashMap' prende i valori di' hashCode() 'dai suoi oggetti e applica una trasformazione" sbiancamento "one-to-one per cercare di rendere la distribuzione più uniforme. – Nayuki

+0

@Andreas Ho accettato la soluzione! Grazie. Potresti collegarmi, o forse spiegare, qual è il potere del mascheramento? Una ricerca su google per il termine prodotto nullo. – Muno

+1

@Muno Il mascheramento della potenza di due fa riferimento al fatto che la dimensione della tabella hash è sempre una potenza di due (2,4,8,16,32, ...), quindi per calcolare il bucket di hash, può essere eseguita una semplice operazione di maschera di bit essere eseguito (ad esempio 'h & 0x1F' per dimensione hashtable 32), che è più veloce di un'operazione a modulo ('% '). – Andreas

Problemi correlati