Wie ist die Datenstruktur HashMap in Java aufgebaut…

HashMap in Java basiert auf Hashing-Prinzipien. Es speichert "Schlüssel-Wert"-Paare.

Interne Struktur:

Array von Buckets (Behältern). Jeder Bucket ist eine verkettete Liste (oder ein Baum, ab Java 8, bei vielen Kollisionen).
Beim Hinzufügen eines Elements (put):
1. Es wird der Hash-Code des Schlüssels berechnet (key.hashCode()).
2. Der Hash-Code wird modifiziert, um eine bessere Verteilung zu erreichen (hash).
3. Mit dem modifizierten Hash und der Größe des Bucket-Arrays wird der Index des Buckets berechnet (hash & (array_size - 1)).
4. Das Element (Schlüssel-Wert-Paar als Node-Objekt) wird in diesen Bucket eingefügt. Wenn der Bucket bereits Elemente enthält, wird das neue Element am Anfang der verketteten Liste oder des Baumes hinzugefügt.
5. Beim Hinzufügen wird geprüft, ob der Schlüssel bereits existiert: Es wird die Methode equals() verwendet, um die Schlüssel im Bucket zu vergleichen. Wenn der Schlüssel gefunden wird, wird der Wert aktualisiert.
Beim Abrufen eines Elements (get):
1. Der Bucket-Index wird ebenfalls anhand des Schlüssels berechnet.
2. Innerhalb des Buckets wird nach dem Element anhand des Schlüssels gesucht, unter Verwendung der Methoden hashCode() und equals().
3. Der zugehörige Wert wird zurückgegeben.

Organisation:

Kollisionen: Wenn mehrere Schlüssel denselben Hash-Code haben und in denselben Bucket fallen, werden die Elemente in einer verketteten Liste gespeichert. Ab Java 8 wird bei Überschreiten eines Schwellenwerts (normalerweise 8) die Liste in einen Baum umgewandelt, um schnellere Suchen zu ermöglichen (O(log n) statt O(n)).
Resizing: Wenn die Anzahl der Elemente den "Ladefaktor" (load factor * capacity) überschreitet, vergrößert HashMap die interne Array-Größe (meist verdoppelt) und berechnet alle Hashes neu. Dies ist eine teure Operation (O(n)).
Parameter:
- capacity: Anfangsgröße des Buckets-Arrays (Standard 16).
- load factor: Schwellenwert für die Auslastung (Standard 0.75). Bestimmt, wann das Resizing erfolgt.

Warum hashCode() und equals() wichtig sind:

Das korrekte Funktionieren von HashMap hängt von der richtigen Implementierung dieser Methoden ab.
Wenn equals() für zwei Objekte true zurückgibt, muss hashCode() denselben Wert liefern.
Eine falsche Implementierung kann dazu führen, dass Elemente nicht gefunden werden (get gibt null zurück), obwohl sie hinzugefügt wurden.

Beispiel für Node-Struktur:

// Nur intern
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;
    }

    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=" + value; }

    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }

    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }

    public final boolean equals(Object o) {
        if (o == this)
            return true;
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}

HashMap bietet schnelles (durchschnittlich O(1)) Hinzufügen, Abrufen und Entfernen von Elementen bei gleichmäßiger Hash-Verteilung. Im schlimmsten Fall (starke Kollisionen) kann die Operation O(n) oder O(log n) mit Bäumen sein.

Nicht thread-sicher. Für den Einsatz in Mehrthread-Umgebungen sollte ConcurrentHashMap oder Collections.synchronizedMap(new HashMap<...>(...)) verwendet werden.

Wie ist die Datenstruktur HashMap in Java aufgebaut und organisiert?