Wie Java HashMaps funktionieren – interne Mechanik erklärt

Ein HashMap ist eine der am häufigsten verwendeten Datenstrukturen in Java und ist bekannt für seine Effizienz. Daten in einem HashMap werden in Form von Schlüssel-Wert-Paaren gespeichert.

In diesem Artikel werde ich Ihnen HashMaps in Java näher bringen. Wir werden die gängigen Operationen von HashMaps erkunden und dann in die internen Mechanismen eintauchen. Sie werden verstehen, wie die Hash-Funktion funktioniert und wie die Indexberechnung stattfindet. Schließlich werden wir uns auf die Zeitkomplexitäten der Operationen konzentrieren und anschließend das Verhalten in einer gleichzeitigen Umgebung behandeln.

Was ist ein `HashMap` in Java?

Ein HashMap implementiert die Map-Schnittstelle, die Teil der Java-Kollektionsarchitektur ist. Es basiert auf dem Konzept des Hashing.

Hashing ist eine Technik, die ein beliebiges Eingabeargument in eine feste Größe umwandelt, indem eine Hash-Funktion verwendet wird. Der generierte Ausgabewert wird Hash-Code genannt und in Java durch einen Integer-Wert repräsentiert. Hash-Codes werden für effiziente Suche und Speicherungsvorgänge in einem HashMap verwendet.

Gängige Operationen

Wie wir oben diskutiert haben, werden Daten in einem HashMap in Form von Schlüssel-Wert-Paaren gespeichert. Der Schlüssel ist ein eindeutiger Identifikator, und jedem Schlüssel ist ein Wert zugeordnet.

Unten sind einige gängige Operationen aufgeführt, die von einem HashMap unterstützt werden. Lassen Sie uns mit einfachen Codebeispielen verstehen, was diese Methoden tun:

Einfügen

Diese Methode fügt ein neues Schlüssel-Wert-Paar in den HashMap ein.
Der Insertions-Order der Schlüssel-Wert-Paare wird nicht aufbewahrt.
Während der Einfügeoperation, falls ein Schlüssel bereits vorhanden ist, wird der bestehende Wert mit dem neuen Wert, der übergeben wird, ersetzt.
Sie können nur einen leeren Schlüssel in den HashMap einfügen, aber Sie können mehrere leere Werte haben.

Die Signatur der Methode für diese Operation ist unten gegeben, gefolgt von einem Beispiel:

public V put(K key, V value)

Map<String, Integer> map = new HashMap<>();
map.put("apple", 1);
map.put("banana", 2);

In dem oben stehenden Code haben wir ein HashMap-Beispiel, in dem wir einen Schlüssel vom Typ String und einen Wert vom Typ Integer hinzufügen.

Auslesen:

Holzt den Wert ab, der mit einem gegebenen Schlüssel assoziiert ist.
Gibt null zurück, wenn der Schlüssel im HashMap nicht existiert.

Die Signatur dieser Methode ist unten gegeben, gefolgt von einem Beispiel:

public V get(Object key)

Integer value = map.get("apple"); // liefert 1

In dem oben stehenden Code holen wir den Wert ab, der mit dem Schlüssel apple assoziiert ist.

Weitere häufige Operationen umfassen:

remove: Entfernt das Key-Value-Paar für den angegebenen Schlüssel. Es liefert null falls der Schlüssel nicht gefunden wird.
containsKey: Prüft, ob ein bestimmter Schlüssel in der HashMap enthalten ist.
containsValue: Prüft, ob der angegebene Wert in der HashMap enthalten ist.

Interner Aufbau einer `HashMap`

Intern nutzt eine HashMap ein Array von Buckets oder Bins. Jeder Bucket ist eine verkettete Liste des Typs Node, die zum Darstellen des Key-Value-Paares der HashMap verwendet wird.

static class Node<K, V> {
    final int hash;
    final K key;
    V value;
    Node<K, V> next;

    Node(int hash, K key, V value, Node<K, V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
}

Oben kannst du die Struktur der Node-Klasse sehen, die zum Speichern der Key-Value-Paare der HashMap verwendet wird.

Die Node-Klasse hat die folgenden Felder:

hash: Bezieht sich auf den hashCode des Schlüssels.
key: Bezieht sich auf den Schlüssel des Key-Value-Paares.
value: Bezieht sich auf den Wert, der dem Schlüssel zugeordnet ist.
next: Dient als Verweis auf den nächsten Knoten.

Der HashMap basiert grundsätzlich auf einer Hash-Tabelle-Implementierung und seine Leistung hängt von zwei wichtigen Parametern ab: der Anfangskapazität und dem Ladefaktor. Die ursprünglichen javadocs der Hash-Tabelle-Klasse definieren diese beiden Parameter folgendermaßen:

Die Kapazität ist die Anzahl der Buckets in der Hash-Tabelle, und die Anfangskapazität ist einfach die Kapazität, die die Hash-Tabelle bei der Erstellung hat.
Der Ladefaktor ist ein Maß für die Belegung der Hash-Tabelle, bis ihre Kapazität automatisch vergrößert wird.

Lassen Sie uns nun versuchen zu verstehen, wie die grundlegenden Operationen put und get in einem HashMap funktionieren.

Hash-Funktion

Während die Einfügeoperation (`put`) eines Schlüssel-Wert-Paares in eine `HashMap` erfolgt, berechnet die `HashMap` zunächst den Hashcode der Schlüssel. Die Hashfunktion bestimmt daraufhin eine Ganzzahl für den Schlüssel. Klassen können die `hashCode` Methode der `Object` Klasse verwenden oder diese Methode überschreiben und ihre eigene Implementierung bereitstellen. (Lesen Sie über den Hash-Code-Vertrag `hier`). Der Hash-Code wird anschließend mit seiner oberen 16 Bit (h `>>>>` 16) per XOR-Operation (exklusives Oder) verarbeitet, um eine höhere Uniformität der Verteilung zu erzielen.`

XOR ist eine bitweise Operation, die zwei Bitwerte vergleicht und 1 ergibt, wenn die Bits unterschiedlich sind, und 0, wenn sie gleich sind. In diesem Kontext verhilft die bitweise XOR-Operation zwischen dem Hash-Code und seiner oberen 16 Bits (erhalten durch Verwendung des ungeraden rechten Shift-Operators `>>>>`) zur Vermischung der Bits und führt zu einer gleichmäßigeren verteilten Hash-Code-Zahl.`

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

oben können Sie die statische Hash-Methode der `HashMap` Klasse sehen.`

Der Ansatz besteht darin, jedem Schlüssel einen eindeutigen Hash-Code zuzuordnen, aber die Hashfunktion könnte den gleichen Hash-Code für verschiedene Schlüssel erzeugen. Dies führt zu einer Situation, die als Kollision bezeichnet wird. Wir werden in der nächsten Abschnitt sehen, wie Kollisionen behandelt werden.`

Indexberechnung

Sobald der Hash-Code für einen Schlüssel berechnet wurde, berechnet die `HashMap` einen Index innerhalb des Arrays der Buckets, um festzustellen, wo das Schlüssel-Wert-Paar gespeichert wird. Dies geschieht mit Hilfe einer bitweisen AND-Operation, was eine effiziente Methode ist, um das Modulo zu berechnen, wenn die Länge des Arrays eine Zweierpotenz ist.

int index = (n - 1) & hash;

Hier berechnen wir den Index, an dem n die Länge des Bucket-Arrays ist.

Sobald der Index berechnet ist, wird die Schlüssel dann an dieser Stelle im Bucket-Array gespeichert. Allerdings verursacht es, wenn mehrere Schlüssel den gleichen Index haben, einen Kollisionsfall. In solcher Situation behandelt das HashMap dies in einer von zwei Wegen:

Ketten/Verknüpfung: Jedes Feld im Array ist eine Kette von Knoten. Wenn bereits ein Schlüssel an einer bestimmten Stelle existiert und ein anderer Schlüssel auf den gleichen Index hascht, wird er der Liste hinzugefügt.
Bäume: Wenn die Anzahl der Knoten einen bestimmten Schwellenwert überschreitet, wird die Kette in ein Baum umgewandelt (Dies wurde in Java 8 eingeführt).

static final int TREEIFY_THRESHOLD = 8;

Dies ist der Schwellenwert, der die Verästelung bestimmt.

Daher ist es wichtig, eine gute Hash-Funktion zu haben, die die Schlüssel gleichmäßig über die Buckets verteilt und die Wahrscheinlichkeit von Kollisionen minimiert.

Die Abfrage (get) und Löschoperation (remove) funktionieren Ähnliches wie die Einfügeoperation (put). So funktioniert es:

Abfrage (get): Berechnet den Hash-Code mit der Hash-Funktion -> berechnet den Index mit dem Hash-Code -> durchsucht die Kette oder den Baum, um den Knoten mit dem passenden Schlüssel zu finden.
Löschen (remove): Berechnet den Hash-Code mithilfe der Hash-Funktion -> berechnet den Index auf Basis des Hash-Codes -> entfernt den Knoten aus der verketteten Liste oder dem Baum.

Zeit Komplexität

Die grundlegenden Operationen einer HashMap, wie put, get und remove, bieten im Allgemeinen eine Konstante Zeitleistung von O(1), vorausgesetzt, die Schlüssel sind gleichmäßig verteilt. In Fällen mit schlechter Schlüsselverteilung und vielen Kollisionen können diese Operationen auf lineare Zeitkomplexität von O(n) abschwächen.

Unter der Baumerstellung, wo lange Ketten von Kollisionen in ausgebalancierte Bäume umgewandelt werden, können Suchoperationen effizienter auf logarithmische Zeitkomplexität von O(log n) verbessert werden.

Synchronisierung

Die HashMap-Implementierung ist nicht synchrone. Wenn mehrere Threads gleichzeitig auf eine HashMap-Instanz zugreifen und über das Mapping iterieren, und wenn einer der Threads eine strukturelle Änderung (wie z.B. die Hinzufügung oder die Löschung einer Schlüssel-Wert-Zuordnung) auf dem Mapping vornimmt, führt das zu einer ConcurrentModificationException.</

Um das zu vermeiden, kannst du mit Hilfe der Methode Collections.synchronizedMap eine thread-sichere Instanz erstellen.

Fazit

Zusammenfassend ist es für Entwickler wichtig, die internen Arbeitsweise eines HashMap zu verstehen, um informierte Entscheidungen treffen zu können. Die Kenntnis, wie ein Schlüssel zugewiesen wird, wie Kollisionen auftreten und wie sie vermieden werden können, hilft dir, den HashMap effizient und wirksam zu verwenden.

Was ist ein HashMap in Java?