HashMap: Geheimräume, Magie und Kollisionen

Stellen wir uns eine HashMap als ein Schloss mit geheimen Räumen (Eimern) vor, wobei jedem Raum magische Türen vorausgehen – Hash-Funktionen. Wie funktioniert dieser magische Mechanismus und was passiert, wenn zwei magische Wesen am selben Ort kollidieren? Tauchen wir ein in die geheime Welt von HashMap. Schauen wir uns zunächst an, woraus eine HashMap besteht.

Grundkomponenten einer HashMap

Tabellenarray: Dieses Array ist der Hauptdatenspeicher. Jede Array-Zelle (oder jeder Bucket) enthält einen eindeutigen Index, in dem Werteketten oder bei einer großen Anzahl von Elementen sogar ein Binärbaum gespeichert werden können.

LoadFactor: LoadFactor gibt an, wie viel eine HashMap gefüllt werden kann, bevor sie erweitert wird. Der Standardlastfaktor beträgt 0,75, wodurch ein Gleichgewicht zwischen Speichereinsparungen und Zugriffsgeschwindigkeit hergestellt wird. Wenn die HashMap zu 75 % gefüllt ist, verdoppelt sie die Größe der Tabelle und verteilt die Elemente neu, um die Effizienz aufrechtzuerhalten.

Schwellenwert: Der Schwellenwert ist der Punkt, an dem die HashMap beschließt, die Tabelle zu erweitern. Berechnet als (Kapazität * Lastfaktor). Wenn die Kapazität beispielsweise 16 und der LoadFactor 0,75 beträgt, liegt der Schwellenwert bei 12. Wenn die HashMap 12 Elemente erreicht, erhöht sie ihre Größe.

Die Größe verfolgt die aktuelle Anzahl der Schlüssel-Wert-Paare in der HashMap.

Jedes Schlüssel-Wert-Paar in einer HashMap wird in einer Struktur namens Node gespeichert, die Folgendes enthält:

Schlüssel – Schlüssel des Paares,
Wert – der Wert des Paares,
hash – Hash berechnet basierend auf dem hashCode()-Schlüssel,
next – ein Link zum nächsten Element in der Kette im Falle von Kollisionen.

static class Node<K, V> implements Map.Entry<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;
    }

    ....
}

Jeder Knoten wird bei einer Kollision mit dem nächsten im selben Bucket verbunden, wodurch eine verknüpfte Liste entsteht. Diese Listen verwandeln sich automatisch in einen ausgeglichenen Binärbaum, wenn sich mehr als acht Elemente im Bucket ansammeln.

Hash-Funktion: Wie Schlüssel ihre Räume finden

Stellen Sie sich vor, dass HashMap ein riesiges Schloss mit vielen Räumen ist. Jedes Zimmer hat eine eindeutige Nummer, aber wie entscheiden die Schlüssel, zu welchem ​​Zimmer man geht? Dies ist die Aufgabe der Hash-Funktion, einem magischen Werkzeug, das dabei hilft, zu bestimmen, in welchen Eimer (Raum) ein bestimmter Schlüssel gelegt wird.

Wenn wir einen Schlüssel hinzufügen, ruft die putVal-Methode die hashCode()-Methode des Schlüssels auf, um einen Hash zu erstellen, der dann verfeinert wird, um gleichmäßig auf die Buckets verteilt zu werden.
Indexberechnung: Mithilfe der Formel int index = hashCode & (length- 1) berechnet HashMap den Index, der auf den Bucket im Tabellenarray zeigt.

Hier ist HashCode der eindeutige Code, den der Schlüssel über die Hash-Funktion erhält. Anschließend führen wir eine bitweise UND-Operation für die Länge - 1 durch. Dies entspricht der Berechnung des Rests des Hash-Codes dividiert durch die Anzahl der Buckets und bestimmt so den Index im Bucket-Array.

import java.util.HashMap;

public class MagicalHashMap {
    public static void main(String[] args) {
        // Создаем новый HashMap
        HashMap<String, String> rooms = new HashMap<>();

        // Добавляем элементы в HashMap
        rooms.put("apple", "A room full of apples");
        rooms.put("banana", "A room full of bananas");

        // Поиск по ключу
        System.out.println("Room for 'apple': " + rooms.get("apple"));
        System.out.println("Room for 'banana': " + rooms.get("banana"));
    }
}

Dadurch durchläuft jeder Schlüssel eine Hash-Funktion und landet in seinem eigenen eindeutigen Raum, dessen Index durch bitweises UND berechnet wird.

Kollisionsprüfung: Wenn der Bucket leer ist, wird ein neues Schlüssel-Wert-Paar hinzugefügt. Wenn nicht, prüft putVal, ob der Schlüssel übereinstimmt:

Entspricht * – der Wert wird aktualisiert.
*Trifft nicht zu - es entsteht ein Konflikt - mehr dazu weiter unten.

Kollisionen: Geheime Räume, die ineinander übergehen

Was passiert, wenn zwei Schlüssel im selben Raum landen (mehrere Schlüssel führen zu einem Eimer)? In HashMap wird dies als Kollision bezeichnet. Dies ist der Fall, wenn zwei Schlüssel denselben Hash-Code haben und versuchen, in denselben Bucket zu gelangen. Wann ist das möglich? Beispielsweise haben wir den Hash-Code fälschlicherweise überschrieben.

static class Node<K, V> implements Map.Entry<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;
    }

    ....
}

In diesem Beispiel verfügt die KeyWithSameHash-Klasse über eine überschriebene hashCode()-Methode, die für alle Instanzen denselben Wert zurückgibt, wodurch alle Schlüssel in derselben Zelle des Tabellenarrays landen:

import java.util.HashMap;

public class MagicalHashMap {
    public static void main(String[] args) {
        // Создаем новый HashMap
        HashMap<String, String> rooms = new HashMap<>();

        // Добавляем элементы в HashMap
        rooms.put("apple", "A room full of apples");
        rooms.put("banana", "A room full of bananas");

        // Поиск по ключу
        System.out.println("Room for 'apple': " + rooms.get("apple"));
        System.out.println("Room for 'banana': " + rooms.get("banana"));
    }
}

Für alle Schlüssel beträgt der hashCode()-Wert 42, sodass der Bucket-Index in der Tabelle jedes Mal, wenn ein Schlüssel hinzugefügt wird, derselbe ist.

Aber statt Köpfe zu stoßen, öffnen die Schlüssel zusätzliche Türen und verwandeln den Raum in einen magischen Korridor, der zu neuen Räumen führt. Diese neuen Räume dienen im Wesentlichen dazu, Kollisionen zu lösen.

Verknüpfte Listen: Wenn zwei Schlüssel mit denselben Hash-Codes im selben Bucket landen, erstellt HashMap eine verknüpfte Liste in diesem Bucket. Die Schlüssel werden weiterhin in dieser Liste gespeichert und bei Bedarf wird mit der Methode equal() überprüft, ob die Schlüssel tatsächlich gleich sind.

Rot-Schwarz-Bäume: Wenn die Anzahl der Kollisionen in einem Bucket zu hoch wird (der Korridor wird zu lang), wandelt HashMap ihn in einen Rot-Schwarz-Baum um. Dies trägt dazu bei, die Suche zu beschleunigen und Verlangsamungen bei hoher Auslastung zu verhindern.

Wie equal() und hashCode() funktionieren

Damit die HashMap-Magie ordnungsgemäß funktioniert, ist es wichtig, dass zwei identische Schlüssel mit demselben Wert dieselben Hash-Codes zurückgeben und auch mithilfe der Methode equal() korrekt verglichen werden. Es ist wie ein Zauberspruch, der prüft, ob zwei Objekte gleich sind, auch wenn sie möglicherweise auf unterschiedliche Weise dargestellt werden.

hashCode(): Jedes Objekt muss seinen eigenen eindeutigen Hash-Code haben. Dadurch kann die HashMap effizient den Bucket finden, in dem der Schlüssel platziert werden muss.
equal(): Wenn zwei Objekte denselben Hashcode haben, prüft die Methode equal(), ob die Objekte tatsächlich gleich sind.
Wäre diese Prüfung nicht vorhanden, könnte HashMap zwei unterschiedliche Schlüssel verwechseln, was zu fehlerhaftem Programmverhalten führen würde.

Abschluss

Die Welt von HashMap ist eine Welt voller Magie, in der Hash-Funktionen und Kollisionen Schlüsseln helfen, ihre Räume zu finden und das Schloss in Ordnung zu halten. Jeder Schlüssel hat seinen eigenen Pfad, der dank einer Hash-Funktion zu einem eindeutigen Index führt. Und wenn zwei Schlüssel im selben Eimer kollidieren, wirkt die Magie weiter und öffnet neue Türen in Form von verknüpften Listen oder rot-schwarzen Bäumen, um den richtigen Weg zu finden.

Dank hashCode(), equal() und magischen Kollisionskorridoren ist HashMap also weiterhin eines der leistungsstärksten Tools im Arsenal eines Java-Entwicklers und garantiert Effizienz und Genauigkeit auch in den verwirrendsten Situationen.

Das obige ist der detaillierte Inhalt vonHashMap: Geheimräume, Magie und Kollisionen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!