Sto osservando l'implementazione di HashMap in Java e sono bloccato in un punto.
Come viene calcolata la funzione indexFor?Implementazione di HashMap in Java. Come funziona il calcolo dell'indice del secchio?
static int indexFor(int h, int length) {
return h & (length-1);
}
Grazie
Non è il calcolo del hash, è il calcolo del secchio.
L'espressione h & (length-1) fa un bit-wise AND su h utilizzando length-1, che è come una maschera di bit, per restituire solo i bit di ordine basso h, rendendo in tal modo per un super-veloce variante h % length.
Sta calcolando il bucket della mappa hash in cui verrà memorizzata la voce (coppia chiave-valore). L'id del secchio è hashvalue/buckets length.
Una mappa di hash è composta da bucket; gli oggetti verranno posizionati in questi bucket in base all'ID bucket.
Qualsiasi numero di oggetti può effettivamente rientrare nello stesso segmento in base al valore hash code/buckets length. Questo è chiamato "collisione".
Se molti oggetti cadono nello stesso bucket, durante la ricerca il loro metodo equals() verrà chiamato per disambiguare.
Il numero di collisioni è indirettamente proporzionale alla lunghezza della benna.
L'hash stesso viene calcolato dal metodo hashCode() dell'oggetto che si sta tentando di memorizzare.
Quello che vedete qui è il calcolo del "bucket" per memorizzare l'oggetto in base all'hash h. Idealmente, per evitare le collisioni, si otterrebbe lo stesso numero di serbatoi pari al massimo valore ottenibile di h, ma potrebbe anche richiedere troppo memoria. Di conseguenza, di solito hai un numero inferiore di secchi con il rischio di collisioni.
Se h è, ad esempio, 1000, ma si dispone solo di 512 bucket nell'array sottostante, è necessario sapere dove posizionare l'oggetto. Di solito, un'operazione mod su h sarebbe sufficiente, ma è troppo lenta. Data la struttura interna del HashMap che la matrice sottostante sempre ha numero di contenitori pari a 2^n, gli ingegneri della Sun potrebbero usare l'idea di h & (length-1), si fa un bitwise AND con un numero consistente di tutti 1 's, praticamente leggere solo il n i bit più bassi dell'hash (che equivale a fare h mod 2^n, solo molto più veloce).
Esempio:
hash h: 11 1110 1000 -- (1000 in decimal)
length l: 10 0000 0000 -- (512 in decimal)
(l-1): 01 1111 1111 -- (511 in decimal - it will always be all ONEs)
h AND (l-1): 01 1110 1000 -- (488 in decimal which is a result of 1000 mod 512)
Ha senso ora, o dovrei elaborare di più sugli interni ? –
_Molto bene spiegato. Sono impressionato. –
capito .... grazie – gnreddy
si può spiegare questo calcolo qui? – gnreddy
Suppone che 'length' sia un potere di 2? – LarsH
@LarsH Beh, sarebbe molto meglio se fosse una potenza di 2, quindi si otterrebbe un taglio pulito dei bit di ordine superiore. Come succede, l'implementazione di HashMap inizia con la dimensione 16 e infatti si moltiplica per due durante il ridimensionamento.Funzionerebbe ancora se non fosse una potenza di due, ma vorrai quanti più "on" bit possibile per 'length -1' per bilanciare lo spread tra i bucket – Bohemian