In che modo una Java HashMap gestisce oggetti diversi con lo stesso codice hash?

Secondo la mia comprensione penso:

  1. È perfettamente legale che due oggetti abbiano lo stesso codice hash.
  2. Se due oggetti sono uguali (usando il metodo equals ()) hanno lo stesso codice hash.
  3. Se due oggetti non sono uguali, non possono avere lo stesso codice hash

Ho ragione?

Ora, se sono corretto, ho la seguente domanda: HashMap usa internamente il codice hash dell’object. Quindi se due oggetti possono avere lo stesso codice hash, allora come può HashMap tracciare quale chiave usa?

Qualcuno può spiegare come HashMap utilizza internamente l’hashcode dell’object?

Una hashmap funziona in questo modo (questo è un po ‘semplificato, ma illustra il meccanismo di base):

Ha un numero di “bucket” che utilizza per memorizzare coppie di valori-chiave. Ogni bucket ha un numero univoco – questo è ciò che identifica il bucket. Quando si inserisce una coppia chiave-valore nella mappa, l’hashmap controlla il codice hash della chiave e memorizza la coppia nel bucket di cui l’identificatore è il codice hash della chiave. Ad esempio: il codice hash della chiave è 235 -> la coppia è memorizzata nel bucket numero 235. (Si noti che un bucket può memorizzare più di una coppia chiave-valore).

Quando cerchi un valore nella hashmap, dandogli una chiave, prima vedrà il codice hash della chiave che hai dato. L’hashmap quindi esaminerà il bucket corrispondente e quindi confronterà la chiave assegnata con le chiavi di tutte le coppie nel bucket, confrontandole con equals() .

Ora puoi vedere come questo sia molto efficace per cercare le coppie chiave-valore in una mappa: tramite il codice hash della chiave l’hashmap sa immediatamente in quale bucket deve essere visualizzato, in modo che debba solo testare cosa c’è in quel bucket.

Osservando il meccanismo sopra, puoi anche vedere quali sono i requisiti necessari sui metodi hashCode() ed equals() delle chiavi:

  • Se due chiavi sono uguali ( equals() restituisce true quando le confronti), il loro metodo hashCode() deve restituire lo stesso numero. Se le chiavi violano questo, le chiavi uguali potrebbero essere archiviate in diversi bucket e l’hashmap non sarebbe in grado di trovare coppie di valori-chiave (perché guarderà nello stesso bucket).

  • Se due chiavi sono diverse, non importa se i loro codici hash sono uguali o meno. Saranno memorizzati nello stesso bucket se i loro codici hash sono uguali, e in questo caso, l’hashmap userà equals() per distinguerli.

La tua terza affermazione non è corretta.

È perfettamente legale per due oggetti non uguali avere lo stesso codice hash. Viene utilizzato da HashMap come “filtro di primo passaggio” in modo che la mappa possa trovare rapidamente le voci possibili con la chiave specificata. Le chiavi con lo stesso codice hash vengono quindi testate per l’uguaglianza con la chiave specificata.

Non si vorrebbe un requisito che due oggetti non uguali non possano avere lo stesso codice hash, altrimenti ciò limiterebbe a 2 32 possibili oggetti. (Significa anche che tipi diversi non potrebbero neanche usare i campi di un object per generare codici hash, dato che altre classi potrebbero generare lo stesso hash.)

Diagramma di struttura HashMap

HashMap è una matrice di oggetti Entry .

Considerare HashMap come una semplice serie di oggetti.

Dai un’occhiata a cosa è questo Object :

 static class Entry implements Map.Entry { final K key; V value; Entry next; final int hash; … } 

Ogni object Entry rappresenta una coppia valore-chiave. Il campo next fa riferimento a un altro object Entry se un bucket ha più di una Entry .

A volte può succedere che i codici hash per 2 oggetti diversi siano gli stessi. In questo caso, due oggetti verranno salvati in un bucket e verranno presentati come un elenco collegato. Il punto di ingresso è l’object aggiunto più di recente. Questo object si riferisce a un altro object con il campo next e così via. L’ultima voce si riferisce a null .

Quando si crea una HashMap con il costruttore predefinito

 HashMap hashMap = new HashMap(); 

La matrice viene creata con la dimensione 16 e il bilancio di carico 0,75 predefinito.

Aggiungere una nuova coppia chiave-valore

  1. Calcola hashcode per la chiave
  2. Calcola posizione hash % (arrayLength-1) dove deve essere posizionato l’elemento (numero bucket)
  3. Se provi ad aggiungere un valore con una chiave che è già stata salvata in HashMap , il valore viene sovrascritto.
  4. Altrimenti l’elemento viene aggiunto al bucket.

Se il bucket ha già almeno un elemento, ne viene aggiunto uno nuovo e posizionato nella prima posizione del bucket. Il suo next campo si riferisce al vecchio elemento.

cancellazione

  1. Calcola hashcode per la chiave specificata
  2. Calcola il numero di hash % (arrayLength-1) numero hash % (arrayLength-1)
  3. Ottieni un riferimento al primo object Entry nel bucket e tramite il metodo equals iterate su tutte le voci nel bucket specificato. Alla fine troveremo la Entry corretta. Se un elemento desiderato non viene trovato, restituisce null

Puoi trovare informazioni eccellenti su http://javarevisited.blogspot.com/2011/02/how-hashmap-works-in-java.html

Riassumere:

HashMap funziona sul principio dell’hashing

put (chiave, valore): HashMap memorizza sia l’object chiave che il valore come Map.Entry. Hashmap applica hashcode (chiave) per ottenere il bucket. se c’è una collisione, HashMap usa LinkedList per memorizzare l’object.

get (chiave): HashMap utilizza l’hashcode dell’object chiave per individuare la posizione del bucket e quindi chiama il metodo keys.equals () per identificare il nodo corretto in LinkedList e restituire l’object valore associato per quella chiave in Java HashMap.

Ecco una descrizione approssimativa del HashMap di HashMap , per la versione Java 8 , (potrebbe essere leggermente diverso da Java 6) .


Strutture dati

  • Tavolo hash
    Il valore hash viene calcolato tramite hash() sulla chiave e decide quale bucket della tabella da utilizzare per una determinata chiave.
  • Elenco collegato (singolarmente)
    Quando il conteggio degli elementi in un bucket è piccolo, viene utilizzato un elenco collegato separatamente.
  • Albero rosso-nero
    Quando il conteggio degli elementi in un bucket è grande, viene utilizzato un albero rosso-nero.

Classi (interni)

  • Map.Entry
    Rappresenta una singola entity framework nella mappa, l’ quadro chiave / valore.
  • HashMap.Node
    Versione elenco collegato del nodo.

    Potrebbe rappresentare:

    • Un secchio di hash.
      Perché ha una proprietà hash.
    • Un nodo in una lista concatenata, (quindi anche il capo della lista collegata) .
  • HashMap.TreeNode
    Versione ad albero del nodo.

Campi (interni)

  • Node[] table
    Il tavolo del secchio, (testa delle liste collegate).
    Se un bucket non contiene elementi, allora è null, quindi occupa solo un riferimento.
  • Set
    entrySet

    Set di entity framework.

  • int size
    Numero di quadro
  • float loadFactor
    Indicare quanto è piena la tabella hash, prima di ridimensionarla.
  • int threshold
    La prossima dimensione in cui ridimensionare.
    Formula: threshold = capacity * loadFactor

Metodi (interni)

  • int hash(key)
    Calcola hash per chiave.
  • Come mappare hash in bucket?
    Usa la seguente logica:

     static int hashToBucket(int tableSize, int hash) { return (tableSize - 1) & hash; } 

A proposito di capacità

Nella tabella hash, la capacità indica il numero di bucket, potrebbe essere ottenuto da table.length .
Inoltre potrebbe essere calcolato tramite threshold e loadFactor , quindi non è necessario definirlo come campo di class.

Potrebbe ottenere la capacità effettiva tramite: capacity()


operazioni

  • Trova quadro per chiave.
    Prima trova il bucket in base al valore hash, quindi collega l’elenco collegato o cerca l’albero ordinato.
  • Aggiungi quadro con chiave.
    Prima trova il secchio in base al valore hash della chiave.
    Quindi prova a trovare il valore:
    • Se trovato, sostituire il valore.
    • Altrimenti, aggiungi un nuovo nodo all’inizio dell’elenco collegato o inserisci nell’albero ordinato.
  • Ridimensiona
    Quando viene raggiunta la threshold , raddoppia la capacità di hashtable ( table.length ), quindi esegue un re-hash su tutti gli elementi per ribuild la tabella.
    Questa potrebbe essere un’operazione costosa.

Prestazione

  • prendere e mettere
    La complessità del tempo è O(1) , perché:
    • Si accede a Bucket tramite indice di array, quindi O(1) .
    • L’elenco collegato in ciascun bucket è di piccola lunghezza, pertanto potrebbe essere visualizzato come O(1) .
    • Anche la dimensione dell’albero è limitata, perché aumenterà la capacità e il re-hash quando aumenterà il conteggio degli elementi, quindi potrebbe visualizzarlo come O(1) , non O(log N) .

Il codice hash determina il bucket da controllare per l’hashmap. Se c’è più di un object nel bucket, viene eseguita una ricerca lineare per trovare quale elemento nel bucket è uguale all’elemento desiderato (utilizzando il metodo equals() ).

In altre parole, se si dispone di un codice hash perfetto, l’accesso hashmap è costante, non sarà mai necessario iterare attraverso un bucket (tecnicamente si dovranno avere anche bucket MAX_INT, l’implementazione Java potrebbe condividere alcuni codici hash nello stesso bucket per ridurre i requisiti di spazio). Se hai il peggiore hashcode (restituisce sempre lo stesso numero), l’accesso a hashmap diventa lineare poiché devi cercare tra tutti gli elementi della mappa (sono tutti nello stesso bucket) per ottenere ciò che desideri.

Il più delle volte un hashcode ben scritto non è perfetto ma è abbastanza unico da darti accesso più o meno costante.

Ti sbagli sul punto tre. Due voci possono avere lo stesso codice hash ma non essere uguali. Dai un’occhiata all’implementazione di HashMap.get da OpenJdk . Puoi vedere che controlla che gli hash siano uguali e che le chiavi siano uguali. Se il punto tre fosse vero, non sarebbe necessario verificare che le chiavi siano uguali. Il codice hash viene confrontato prima della chiave perché il primo è un confronto più efficiente.

Se sei interessato a saperne un po ‘di più su questo, dai un’occhiata all’articolo di Wikipedia sulla risoluzione delle collisioni Open Address , che credo sia il meccanismo utilizzato dall’implementazione di OpenJdk. Questo meccanismo è sottilmente diverso dall’approccio “secchio” che una delle altre risposte menziona.

Questa è una domanda molto confusa per molti di noi nelle interviste. Ma non è così complessa.

Sappiamo

  • HashMap memorizza la coppia chiave-valore in Map.Entry (lo sappiamo tutti)

  • HashMap lavora sull’algoritmo di hashing e usa il metodo hashCode () e equals () nei metodi put () e get (). (anche noi lo sappiamo)

  • When we call put method by passing key-value pair, HashMap uses Key **hashCode()** with hashing to **find out the index** to store the key-value pair. (this is important)

  • The Entry is **stored in the LinkedList**, so if there are already existing entry, it uses **equals() method to check if the passed key already exists** (even this is important)

  • in caso affermativo, sovrascrive il valore , crea una nuova voce e memorizza questa voce valore-chiave.

  • Quando chiamiamo get metodo passando Key, di nuovo usa hashCode () per trovare l’indice nell’array e quindi usa il metodo equals () per trovare la voce corretta e restituirne il valore. (ora questo è ovvio)

QUESTA IMMAGINE VI AIUTA A CAPIRE:

Modifica settembre 2017: qui vediamo come valore hash se usato insieme agli uguali dopo aver trovato il bucket.

 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { } 

inserisci la descrizione dell'immagine qui

 import java.util.HashMap; public class Students { String name; int age; Students(String name, int age ){ this.name = name; this.age=age; } @Override public int hashCode() { System.out.println("__hash__"); final int prime = 31; int result = 1; result = prime * result + age; result = prime * result + ((name == null) ? 0 : name.hashCode()); return result; } @Override public boolean equals(Object obj) { System.out.println("__eq__"); if (this == obj) return true; if (obj == null) return false; if (getClass() != obj.getClass()) return false; Students other = (Students) obj; if (age != other.age) return false; if (name == null) { if (other.name != null) return false; } else if (!name.equals(other.name)) return false; return true; } public static void main(String[] args) { Students S1 = new Students("taj",22); Students S2 = new Students("taj",21); System.out.println(S1.hashCode()); System.out.println(S2.hashCode()); HashMap HM = new HashMap (); HM.put(S1, "tajinder"); HM.put(S2, "tajinder"); System.out.println(HM.size()); } } Output: __ hash __ 116232 __ hash __ 116201 __ hash __ __ hash __ 2 

Quindi qui vediamo che se entrambi gli oggetti S1 e S2 hanno contenuti diversi, allora siamo abbastanza sicuri che il nostro metodo Hashcode sovrascritto genererà Hashcode diverso (116232,11601) per entrambi gli oggetti. ORA dato che ci sono diversi codici hash, quindi non si preoccuperà nemmeno di chiamare il metodo EQUALS. Perché un Hashcode diverso GARANTISCE un contenuto DIVERSO in un object.

  public static void main(String[] args) { Students S1 = new Students("taj",21); Students S2 = new Students("taj",21); System.out.println(S1.hashCode()); System.out.println(S2.hashCode()); HashMap HM = new HashMap (); HM.put(S1, "tajinder"); HM.put(S2, "tajinder"); System.out.println(HM.size()); } } Now lets change out main method a little bit. Output after this change is __ hash __ 116201 __ hash __ 116201 __ hash __ __ hash __ __ eq __ 1 We can clearly see that equal method is called. Here is print statement __eq__, since we have same hashcode, then content of objects MAY or MAY not be similar. So program internally calls Equal method to verify this. Conclusion If hashcode is different , equal method will not get called. if hashcode is same, equal method will get called. Thanks , hope it helps. 

La mappa di hash funziona sul principio dell’hashing

Il metodo HashMap get (Key k) chiama il metodo hashCode sull’object chiave e applica hashValue restituito alla propria funzione di hash statica per trovare una posizione del bucket (backing array) dove le chiavi e i valori sono archiviati sotto forma di una class nidificata chiamata Entry (Map. Voce). Quindi hai concluso che dalla riga precedente che sia la chiave che il valore sono memorizzati nel bucket come una forma di object Entry. Quindi, pensare che solo il valore è memorizzato nel secchio non è corretto e non darà una buona impressione all’intervistatore.

  • Ogni volta che chiamiamo il metodo get (Key k) sull’object HashMap. Prima controlla che la chiave sia nullo o no. Nota che può esistere una sola chiave nullo in HashMap.

Se la chiave è nullo, le chiavi Null si associano sempre all’hash 0, quindi all’indice 0.

Se la chiave non è nullo, chiamerà hashfunction sull’object chiave, vedere la riga 4 nel metodo precedente, ad es. Key.hashCode (), quindi dopo key.hashCode () restituisce hashValue, la riga 4 assomiglia

  int hash = hash(hashValue) 

e ora applica hashValue restituito alla propria funzione di hashing.

Potremmo chiederci perché stiamo calcolando di nuovo l’hashvalue usando hash (hashValue). La risposta è Difesa contro le funzioni hash di scarsa qualità.

Ora l’hashval finale viene utilizzato per trovare la posizione del bucket in cui è archiviato l’object Entry. L’object entry memorizza nel bucket in questo modo (hash, key, value, bucketindex)

Ogni object Entry rappresenta una coppia chiave-valore. Il campo successivo si riferisce ad un altro object Entry se un bucket ha più di 1 Entry.

A volte può succedere che hashCodes per 2 oggetti diversi siano gli stessi. In questo caso, 2 oggetti verranno salvati in un bucket e verranno presentati come LinkedList. Il punto di ingresso è l’object aggiunto più recentemente. Questo object si riferisce ad un altro object con il campo successivo e quindi uno. L’ultima voce si riferisce a null. Quando crei HashMap con il costruttore predefinito

L’array viene creato con la dimensione 16 e il bilanciamento del carico predefinito di 0,75.

inserisci la descrizione dell'immagine qui

(Fonte)

Non entrerò nei dettagli di come funziona HashMap, ma fornirò un esempio in modo che possiamo ricordare come funziona HashMap rapportandolo alla realtà.

Abbiamo Key, Value, HashCode e bucket.

Per qualche tempo, metteremo in relazione ognuno di essi con il seguente:

  • Secchio -> Una società
  • HashCode -> Indirizzo della società (sempre unico)
  • Valore -> Una casa nella società
  • Chiave -> Indirizzo della casa.

Utilizzando Map.get (chiave):

Stevie vuole arrivare alla casa del suo amico (Josse) che vive in una villa in una società VIP, lascia che sia JavaLovers Society. L’indirizzo di Josse è il suo SSN (che è diverso per tutti). C’è un indice mantenuto in cui scopriamo il nome della società basato su SSN. Questo indice può essere considerato come un algoritmo per scoprire il codice Hash.

  • Nome della società SSN
  • 92313 (Josse’s) – JavaLovers
  • 13214 – AngularJSLovers
  • 98080 – JavaLovers
  • 53808 – BiologyLovers

  1. Questo SSN (chiave) ci fornisce innanzitutto un codice hash (dalla tabella degli indici) che non è altro che il nome della società.
  2. Ora, molte case possono essere nella stessa società, quindi il codice Hash può essere comune.
  3. Supponiamo che la società sia comune per due case, come possiamo identificare la casa in cui ci troviamo, sì, usando la chiave (SSN) che non è altro che l’indirizzo della casa

Utilizzo di Map.put (chiave, valore)

Questo trova una società adatta per questo valore trovando il codice hash e quindi il valore viene memorizzato.

Spero che questo aiuti e questo è aperto per le modifiche.

In una forma estiva di Come hashMap funziona in java?

HashMap funziona sul principio dell’hashing, abbiamo messo () e il metodo get () per l’archiviazione e il recupero dell’object da HashMap. Quando passiamo sia chiave che valore al metodo put () per l’archiviazione su HashMap, utilizza il metodo hashcode () dell’object chiave per calcolare hashcode e, applicando l’hashing su quel hashcode, identifica la posizione del bucket per la memorizzazione dell’object valore. Durante il recupero, utilizza il metodo chiave equals degli oggetti per trovare la coppia di valori chiave corretta e l’object valore di ritorno associato a quella chiave. HashMap utilizza l’elenco collegato in caso di collisione e l’object verrà memorizzato nel nodo successivo dell’elenco collegato. Inoltre HashMap memorizza sia tuple chiave + valore in ogni nodo dell’elenco collegato.

due oggetti sono uguali, implica che hanno lo stesso codice hash, ma non viceversa

Aggiornamento di Java 8 in HashMap-

fai questa operazione nel tuo codice –

 myHashmap.put("old","key-value-pair"); myHashMap.put("very-old","old-key-value-pair"); 

quindi, supponiamo che il tuo hashcode sia tornato per entrambe le chiavi "old" e "very-old" è lo stesso. Quindi cosa accadrà.

myHashMap è una HashMap e supponiamo che inizialmente non ne specificassi la capacità. Quindi la capacità predefinita come per java è 16. Quindi ora non appena inizializzato hashmap usando la nuova parola chiave, ha creato 16 bucket. ora quando hai eseguito la prima dichiarazione-

 myHashmap.put("old","key-value-pair"); 

quindi viene calcolato hashcode per "old" e poiché l’hashcode potrebbe essere anche un numero intero molto grande, quindi java internamente ha fatto questo – (hash hashcode qui e >>> è right shift)

 hash XOR hash >>> 16 

in modo da dare come immagine più grande restituirà un indice, che sarebbe compreso tra 0 e 15. Ora la coppia di valori chiave "old" e "key-value-pair" verrebbe convertita nella variabile di istanza chiave e valore dell’object Entry. e quindi questo object entry verrà memorizzato nel bucket, oppure si può dire che in un particolare indice, questo object entry verrà memorizzato.

FYI- Entry è una class in Map interface- Map.Entry, con questa firma / definizione

 class Entry{ final Key k; value v; final int hash; Entry next; } 

ora quando esegui la prossima dichiarazione –

 myHashmap.put("very-old","old-key-value-pair"); 

e "very-old" restituisce lo stesso hashcode come "old" , quindi questa nuova coppia di valori chiave viene nuovamente inviata allo stesso indice o allo stesso bucket. Ma poiché questo bucket non è vuoto, la next variabile dell’object Entry viene utilizzata per memorizzare questa nuova coppia di valori chiave.

e questo sarà memorizzato come lista collegata per ogni object che ha lo stesso codice hash, ma un TRIEFY_THRESHOLD è specificato con il valore 6. così dopo questo raggiunge, l’elenco collegato viene convertito nell’albero bilanciato (albero rosso-nero) con il primo elemento come radice.

Come si dice, un’immagine vale 1000 parole. Dico: alcuni codici sono migliori di 1000 parole. Ecco il codice sorgente di HashMap. Ottieni il metodo:

 /** * Implements Map.get and related methods * * @param hash hash for key * @param key the key * @return the node, or null if none */ final Node getNode(int hash, Object key) { Node[] tab; Node first, e; int n; K k; if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { if (first.hash == hash && // always check first node ((k = first.key) == key || (key != null && key.equals(k)))) return first; if ((e = first.next) != null) { if (first instanceof TreeNode) return ((TreeNode)first).getTreeNode(hash, key); do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } return null; } 

Quindi diventa chiaro che l’hash è usato per trovare il “bucket” e il primo elemento è sempre controllato in quel bucket. In caso contrario, viene utilizzato il valore equals della chiave per trovare l’elemento effettivo nell’elenco collegato.

Vediamo il metodo put() :

  /** * Implements Map.put and related methods * * @param hash hash for key * @param key the key * @param value the value to put * @param onlyIfAbsent if true, don't change existing value * @param evict if false, the table is in creation mode. * @return previous value, or null if none */ final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node[] tab; Node p; int n, i; if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { Node e; K k; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; else if (p instanceof TreeNode) e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value); else { for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; if (++size > threshold) resize(); afterNodeInsertion(evict); return null; } 

È leggermente più complicato, ma diventa chiaro che il nuovo elemento viene inserito nella scheda nella posizione calcasting in base all’hash:

i = (n - 1) & hash here i è l’indice in cui verrà inserito il nuovo elemento (o è il “bucket”). n è la dimensione della tabarray (matrice di “bucket”).

In primo luogo, si cerca di essere messo come primo elemento di quel “secchio”. Se esiste già un elemento, quindi aggiungere un nuovo nodo all’elenco.

Sarà una lunga risposta, prendi un drink e leggi su …

Hashing consiste nell’archiviazione di una coppia chiave-valore in memoria che può essere letta e scritta più velocemente. Memorizza le chiavi in ​​una matrice e valori in una lista collegata.

Diciamo che voglio memorizzare 4 coppie di valori chiave –

 { “girl” => “ahhan” , “misused” => “Manmohan Singh” , “horsemints” => “guess what”, “no” => “way” } 

Quindi per memorizzare le chiavi abbiamo bisogno di un array di 4 elementi. Ora, come posso mappare uno di questi 4 tasti a 4 indici di array (0,1,2,3)?

Quindi java trova l’hashCode di singole chiavi e le mappa su un particolare indice di array. Hashcode Formule è –

 1) reverse the string. 2) keep on multiplying ascii of each character with increasing power of 31 . then add the components . 3) So hashCode() of girl would be –(ascii values of l,r,i,g are 108, 114, 105 and 103) . eg girl = 108 * 31^0 + 114 * 31^1 + 105 * 31^2 + 103 * 31^3 = 3173020 

Hash e ragazza !! So cosa stai pensando. Il tuo fascino per quel duetto selvaggio potrebbe farti perdere una cosa importante.

Perché java lo moltiplica con 31?

È perché, 31 è un numero primo dispari nella forma 2 ^ 5 – 1. E il primo dispari riduce la possibilità di Hash Collision

Ora, come questo codice hash è mappato a un indice di array?

risposta è, Hash Code % (Array length -1) . Quindi “girl” è mappata a (3173020 % 3) = 1 nel nostro caso. che è il secondo elemento dell’array.

e il valore “ahhan” è memorizzato in una lista collegata associata con l’indice 1 dell’array.

HashCollision – Se provi a trovare hasHCode dei tasti “misused” “horsemints” e “horsemints” usando le formule descritte sopra, vedrai entrambi dandoci lo stesso 1069518484 . Whooaa !! lezione imparata –

2 oggetti uguali devono avere lo stesso hashCode ma non vi è alcuna garanzia se l’hashCode corrisponde a che gli oggetti sono uguali. Quindi dovrebbe memorizzare entrambi i valori corrispondenti a “misused” e “horsemints” al bucket 1 (1069518484% 3).

Ora la mappa di hash sembra –

 Array Index 0 – Array Index 1 - LinkedIst (“ahhan” , “Manmohan Singh” , “guess what”) Array Index 2 – LinkedList (“way”) Array Index 3 – 

Ora se qualche corpo cerca di trovare il valore per la chiave “horsemints” , java troverà rapidamente l’hashCode di esso, lo moduli e inizierà a cercare il suo valore nell’indice corrispondente di LinkedList index 1 . Quindi in questo modo non è necessario cercare tutti i 4 indici di array, rendendo così l’accesso ai dati più veloce.

Ma aspetta un secondo. ci sono 3 valori in quell’indice di array 1 corrispondente a linkedList, come si scopre quale era il valore per la chiave “horsemints”?

In realtà ho mentito, quando ho detto che HashMap memorizza i valori in LinkedList.

Memorizza sia la coppia di valori chiave che la voce della mappa. Quindi in realtà la mappa sembra così.

 Array Index 0 – Array Index 1 - LinkedIst (< ”girl” => “ahhan”> , < ” misused” => “Manmohan Singh”> , < ”horsemints” => “guess what”>) Array Index 2 – LinkedList (< ”no” => “way”>) Array Index 3 – 

Ora puoi vedere Mentre attraversi la lista collegata che corrisponde a ArrayIndex1 confronta effettivamente la chiave di ogni voce di quella LinkedList con “horsemints” e quando ne trova una restituisce semplicemente il valore di essa.

Spero ti sia divertito mentre lo leggevi 🙂