Come funziona HashMap in Java

La maggior parte di voi sarà d'accordo sul fatto che HashMap, oggi, è l'argomento preferito di discussione durante le interviste. A volte ho avuto discussioni simili con i miei colleghi e questo mi ha davvero aiutato. Ora avrò una discussione del genere con te. Presumo che se sei interessato agli aspetti interni e al funzionamento di HashMap, allora hai già familiarità con le basi di HashMap , quindi salterò quella parte. Ma se sei nuovo a questo, ti suggerisco di andare al sito Java Docs . Prima di proseguire, ti consiglio vivamente di consultare il mio articolo precedente: Lavorare con hashCode e il metodo equals in Java. Contenuto di questo articolo:

1. L'unica risposta possibile.
2. Cos'è l'hashing.
3. Un po' della lezione Entry.
4. Cosa fa il put().
5. Come funziona il metodo get().
6. Appunti

L'unica risposta possibile

Se qualcuno mi chiede di spiegare " Come funziona HashMap?" ", risponderò semplicemente: " Secondo i principi dell'Hashing ". Non potrebbe essere più semplice. Per capirlo e ottenere una risposta esaustiva, devi essere sicuro di conoscere le basi dell'Hashing. Giusto?

Cos'è l'hashing

L'hashing nella sua forma più semplice è un modo per convertire qualsiasi variabile/oggetto in un codice univoco dopo aver applicato qualsiasi formula/algoritmo alle relative proprietà. Una vera funzione hash deve seguire la seguente regola: una funzione hash deve restituire lo stesso codice hash ogni volta che viene applicata agli oggetti uguali o uguali. In altre parole, due oggetti identici devono restituire a turno gli stessi codici hash. Puoi leggere ulteriori informazioni al riguardo qui: Lavorare con hashCode e il metodo equals in Java

Un po' della classe Entry

Per definizione, una mappa è “un oggetto che memorizza valori e chiavi in ​​coppia”. Abbastanza semplice, vero? Quindi, deve esserci una sorta di meccanismo in HashMap che memorizza coppie di valori e chiavi? Risposta: sì. HashMapha una classe interna Entryche assomiglia a questa:

static class Entry implements Map.Entry
{
        final K key;
        V value;
        Entry next;
        final int hash;
        ...//остальной code тут…
}

Naturalmente, la classe Entryha una chiave e un valore memorizzati come attributi. La chiave è contrassegnata come finale vediamo anche due campi aggiuntivi: nexte hash. Cercheremo di comprendere lo scopo di questi campi man mano che l'articolo avanza.

Cosa fa il metodo Java put()?

Prima di immergerci nell'implementazione del metodo put(), è molto importante capire che le istanze di una classe Entrysono archiviate in un array. La classe HashMap definisce questa variabile come:

/**
* Размер таблицы, изменяется при необходимости. Длина всегда должна быть
* кратна двум!
*/
    transient Entry[] table;

Ora dai un'occhiata al codice di implementazione del metodo put():

/**
* Связывает определенное meaning с определенным ключом в этой карте(map).
* Если карта перед этим содержала meaning для данного ключа, это meaning
* заменится на новое.
*
* @param key
*            ключ с которым указанное meaning должно быть связано.
* @param value
*            meaning которое должно быть связано с ключом.
* @return вернет предыдущее meaning связанное с key, or null
*         если не было значений связанных с key. (Вернет null
*         так же, если перед этим key был связан со meaningм null)
*/
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry<k , V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}

modCount++;
addEntry(hash, key, value, i);
return null;
}

Scopriamolo passo dopo passo:

• Prima di tutto controlliamo se la chiave esiste. Se la chiave non esiste ( null), il valore viene inserito nella tabella alla posizione zero perché il codice hash per il valore è null, это – всегда 0.


• Nel passaggio successivo si calcola il valore hash utilizzando il codice hash della chiave ottenuto richiamando il metodo hashCode(). Questo valore hash viene utilizzato per calcolare la posizione nell'array in cui verrà posizionato l'oggetto Entry. I progettisti JDK presupponevano che una funzione scritta male hashCode()potesse restituire un valore hash troppo alto o troppo basso. Per risolvere questo problema, hanno introdotto un'altra hash()funzione e vi hanno passato il valore hash di un oggetto per fare in modo che il valore hash corrispondesse alla dimensione dell'array.


• Ora viene chiamata la funzione indexFor(hash, table.length)per calcolare la posizione esatta in cui verrà posizionato l'oggetto Entry.


• È qui che inizia la parte principale. Ora, in base a ciò che sappiamo che due oggetti non uguali possono avere codici hash uguali, poniamo la domanda: due oggetti diversi verranno posizionati nella stessa posizione nell'array [bucket]? La risposta è LinkedList. Se ricordi, la classe Entryha un attributo " next". Questo attributo punta sempre all'oggetto successivo nella catena. Questo è esattamente il comportamento LinkedList.

Pertanto, gli oggetti Entryvengono archiviati nel formato LinkedList. Quando un oggetto Entrydeve essere posizionato in una posizione specifica, HashMap controlla se esiste già una voce in quella posizione. Se non è presente alcuna voce, l'oggetto viene posizionato in questa posizione. Se tuttavia in questa posizione è già presente un oggetto, viene controllato l'attributo successivo. Se ritorna nulle l'oggetto corrente Entrydiventa il collegamento successivo nel file LinkedList. Se la variabile successiva non è null, la procedura viene ripetuta per quella successiva finché non viene trovata null. E se mettessimo un altro oggetto con un valore diverso ma con la stessa chiave di prima? Logicamente questo dovrebbe comportare la sostituzione del vecchio valore. Come avviene questo? In generale, dopo aver determinato la posizione di un oggetto Entry, mentre si raggiunge LinkedListla posizione calcolata, HashMaprichiama il metodo di confronto dei tasti per ciascun oggetto Entry. Tutti questi Entryoggetti LinkedListpossono avere codici hash simili, ma il metodo equals()verificherà la reale somiglianza. Questo sostituirà solo il valore all'interno di Entry. Pertanto, HashMap garantisce l'unicità di tutte le chiavi.

Come funziona il metodo Java get()?

Ora abbiamo un'idea di come vengono archiviate le coppie chiave-valore nei file HashMap. La prossima grande domanda è: cosa succede quando un oggetto viene passato da una HashMap a un metodo get()? Come viene determinato il valore di un oggetto? Dovremmo già conoscere la risposta, perché il modo in cui viene determinata l'unicità di una chiave nel metodo put()ha la stessa logica che applica il metodo get(). Una volta HashMapdeterminata la chiave dell'oggetto passato come argomento, restituisce semplicemente il valore del corrispondente Entry. Se non viene trovata alcuna corrispondenza, il metodo get()restituirà null. Diamo un'occhiata al codice:

public V get(Object key) {
if (key == null)
return getForNullKey();
int hash = hash(key.hashCode());
for (Entry<k,V>e=table[indexFor(hash,table.length)];e!=null;e=e.next){
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
return e.value;
}
return null;
}

Il codice riportato sopra è simile al metodo utilizzato put()fino a questo punto if (e.hash == hash && ((k = e.key) == key || key.equals(k))), dopodiché restituisce semplicemente il valore dell'oggetto.

Appunti

• La struttura dati da memorizzare in un oggetto Entryè un array con un nome tablee un tipo Entry.
• Ogni singola posizione nell'array è chiamata bucket perché può contenere il primo elemento LinkedListdegli oggetti Entry.
• hashCode()La chiave è necessaria per calcolare la posizione dell'oggetto Entry.
• equals()La chiave viene utilizzata per verificare l'unicità della chiave nella mappa ( map).
• hashCode()e equals()i valori non vengono utilizzati nei metodi get()e set()nei file HashMap.
• Il codice hash per le chiavi con un valore nullè sempre 0. E tale oggetto Entryverrà sempre archiviato nella posizione zero dell'array.

Spero di aver espresso correttamente i miei pensieri in questo articolo. Se trovi errori o hai domande, lasciale nei commenti. Buon apprendimento!