Wie funktioniert HashMap in Java?

Die meisten von Ihnen werden zustimmen, dass HashMapheute das beliebteste Diskussionsthema in Vorstellungsgesprächen ist. Manchmal hatte ich ähnliche Diskussionen mit meinen Kollegen und es hat wirklich geholfen. Jetzt werde ich eine solche Diskussion mit Ihnen führen. Ich gehe davon aus, dass Sie, wenn Sie sich für die Interna und Funktionsweise von HashMap interessieren, bereits mit den Grundlagen von HashMap vertraut sind , daher werde ich diesen Teil überspringen. Aber wenn Sie neu in diesem Bereich sind, empfehle ich Ihnen, die Java Docs- Site aufzusuchen . Bevor wir fortfahren, empfehle ich Ihnen dringend, meinen vorherigen Artikel zu lesen: Arbeiten mit HashCode und der Methode equal in Java. Inhalt dieses Artikels:

1. Die einzig mögliche Antwort.
2. Was ist Hashing?
3. Ein wenig über die Klasse Entry.
4. Was bedeutet die put().
5. Wie die Methode funktioniert get().
6. Anmerkungen

Die einzig mögliche Antwort

Wenn mich jemand bittet, zu erklären: „ Wie funktioniert HashMap?“ „, antworte ich einfach: „ Nach den Prinzipien des Hashing .“ Es könnte nicht einfacher sein. Um dies zu verstehen und eine ausführlichere Antwort zu erhalten, müssen Sie sicher sein, dass Sie die Grundlagen des Hashing kennen. Rechts?

Was ist Hashing?

Hashing in seiner einfachsten Form ist eine Möglichkeit, jede Variable/jedes Objekt in einen eindeutigen Code umzuwandeln, nachdem eine Formel/ein Algorithmus auf ihre Eigenschaften angewendet wurde. Eine echte Hash-Funktion muss der folgenden Regel folgen: Eine Hash-Funktion muss immer denselben Hash-Code zurückgeben, wenn sie auf dieselben oder gleiche Objekte angewendet wird. Mit anderen Worten: Zwei identische Objekte müssen nacheinander dieselben Hash-Codes zurückgeben. Mehr dazu können Sie hier lesen: Arbeiten mit HashCode und der Methode equal in Java

Ein wenig über die Einstiegsklasse

Per Definition ist eine Karte „ein Objekt, das Werte und Schlüssel paarweise speichert“. Ziemlich einfach, oder? Es muss also in HashMap einen Mechanismus geben, der Werte- und Schlüsselpaare speichert? Antwort: Ja. HashMaphat eine innere Klasse Entry, die so aussieht:

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

Natürlich Entryverfügt die Klasse über einen Schlüssel und einen Wert, die als Attribute gespeichert sind. Der Schlüssel ist als markiert finalund wir sehen außerdem zwei zusätzliche Felder: nextund hash. Wir werden versuchen, den Zweck dieser Felder im Verlauf des Artikels zu verstehen.

Was macht die Java-Methode put()?

Bevor wir uns mit der Implementierung der Methode befassen put(), ist es sehr wichtig zu verstehen, dass Instanzen einer Klasse Entryin einem Array gespeichert werden. Die HashMap-Klasse definiert diese Variable als:

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

Schauen Sie sich nun den Methodenimplementierungscode an put():

/**
* Связывает определенное Bedeutung с определенным ключом в этой карте(map).
* Если карта перед этим содержала Bedeutung для данного ключа, это Bedeutung
* заменится на новое.
*
* @param key
*            ключ с которым указанное Bedeutung должно быть связано.
* @param value
*            Bedeutung которое должно быть связано с ключом.
* @return вернет предыдущее Bedeutung связанное с key, oder null
*         если не было значений связанных с key. (Вернет null
*         так же, если перед этим key был связан со Bedeutungм 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;
}

Lassen Sie es uns Schritt für Schritt herausfinden:

• Zunächst prüfen wir, ob der Schlüssel existiert. Wenn der Schlüssel nicht vorhanden ist ( ), wird der Wert in der Tabelle an Position Null platziert, da der Hash-Code für den Wert , nulllautet .nullэто – всегда 0


• Im nächsten Schritt wird der Hashwert anhand des Hashcodes des durch den Aufruf der Methode erhaltenen Schlüssels berechnet hashCode(). Dieser Hashwert wird verwendet, um die Position im Array zu berechnen, an der das Objekt platziert wird Entry. Die JDK- Designer gingen davon aus, dass eine schlecht geschriebene Funktion hashCode()einen zu hohen oder zu niedrigen Hashwert zurückgeben könnte. Um dieses Problem zu lösen, führten sie eine weitere hash()Funktion ein und übergaben ihr den Hash-Wert eines Objekts, damit der Hash-Wert mit der Größe des Arrays übereinstimmt.


• Jetzt wird die Funktion aufgerufen indexFor(hash, table.length), um die genaue Position zu berechnen, an der das Objekt platziert wird Entry.


• Hier beginnt der Hauptteil. Basierend auf dem, was wir wissen, dass zwei ungleiche Objekte gleiche Hash-Codes haben können, stellen wir nun die Frage: Werden zwei verschiedene Objekte an derselben Position im [Bucket]-Array platziert? Die Antwort lautet LinkedList. EntryWenn Sie sich erinnern, hat die Klasse ein Attribut „ next“. Dieses Attribut zeigt immer auf das nächste Objekt in der Kette. Genau das ist das Verhalten LinkedList.

Objekte werden also Entryim Formular gespeichert LinkedList. Wenn ein Objekt Entryan einem bestimmten Ort platziert werden soll, prüft HashMap, ob an diesem Ort bereits ein Eintrag vorhanden ist. Ist kein Eintrag vorhanden, wird das Objekt an dieser Position platziert. Befindet sich an dieser Position jedoch bereits ein Objekt, wird das nächste Attribut überprüft. Wenn es zurückkehrt nullund das aktuelle Objekt Entryzum nächsten Link in der LinkedList. Wenn die nächste Variable nicht vorhanden ist null, wird der Vorgang für die nächste wiederholt, bis gefunden wird null. Was wäre, wenn wir ein anderes Objekt mit einem anderen Wert, aber demselben Schlüssel wie zuvor einfügen würden? Logischerweise sollte dies dazu führen, dass der alte Wert ersetzt wird. Wie kommt es dazu? Im Allgemeinen wird nach der Bestimmung der Position eines Objekts Entrybeim Durchlaufen LinkedListder berechneten Position HashMapdie Schlüsselvergleichsmethode für jedes Objekt aufgerufen Entry. Alle diese EntryObjekte LinkedListkönnen ähnliche Hash-Codes haben, die Methode equals()prüft jedoch, ob tatsächliche Ähnlichkeit vorliegt. Dadurch wird nur der Wert innerhalb der ersetzt Entry. Somit garantiert HashMap die Eindeutigkeit aller Schlüssel.

Wie funktioniert die Java-Methode get()?

Jetzt haben wir eine Vorstellung davon, wie Schlüssel-Wert-Paare in gespeichert werden HashMap. Die nächste große Frage lautet: Was passiert, wenn ein Objekt von einer HashMap an eine Methode übergeben wird get()? Wie wird der Wert eines Gegenstandes bestimmt? Wir sollten die Antwort bereits kennen, da die Art und Weise, wie die Eindeutigkeit eines Schlüssels in der Methode bestimmt wird, put()derselben Logik folgt, die die Methode anwendet get(). Sobald HashMapder Schlüssel des als Argument übergebenen Objekts ermittelt wurde, wird einfach der Wert des entsprechenden Objekts zurückgegeben Entry. Wenn keine Übereinstimmungen gefunden werden, get()gibt die Methode zurück null. Werfen wir einen Blick auf den Code:

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;
}

Der obige Code ähnelt der Methode put()bis zu diesem Punkt if (e.hash == hash && ((k = e.key) == key || key.equals(k))). Danach gibt er einfach den Wert des Objekts zurück.

Anmerkungen

• Die in einem Objekt zu speichernde Datenstruktur Entryist ein Array mit einem Namen tableund einem Typ Entry.
• Jede einzelne Position im Array wird als Bucket bezeichnet, da sie das erste Element LinkedListder Objekte enthalten kann Entry.
• hashCode()Der Schlüssel wird benötigt, um die Position des Objekts zu berechnen Entry.
• equals()Der Schlüssel wird verwendet, um die Eindeutigkeit des Schlüssels in der Karte ( map) zu überprüfen.
• hashCode()und equals()Werte werden in Methoden get()und set()in nicht verwendet HashMap.
• Der Hash-Code für Schlüssel mit einem Wert nullist immer 0. Und ein solches Objekt Entrywird immer an der Nullposition des Arrays gespeichert.

Ich hoffe, dass ich meine Gedanken in diesem Artikel richtig ausgedrückt habe. Wenn Sie Fehler finden oder Fragen haben, hinterlassen Sie diese bitte in den Kommentaren. Viel Spaß beim Lernen!