Java Academy · Lektion

Funktionsweise von HashMap

Buckets, Hashing und Kollisionen

Funktionsweise von HashMap ist eine kostenlose Java Academy-Lektion auf CoddyKit. Dies ist Lektion 1 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des Java Academy-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Java Academy-Kurs umfasst insgesamt 4 Lektionen.

Was HashMap speichert

Eine HashMap speichert Schlüssel-Wert-Paare und bietet Ihnen bei Suche, Einfügen und Entfernen durchschnittlich O(1).

Intern enthält sie ein Array namens table. Jeder Platz in diesem Array wird bucket genannt.

Der Schlüssel bestimmt, in welchem Bucket ein Eintrag landet.
Der Wert ist das Ergebnis, das Sie beim Nachschlagen des Schlüssels erhalten.

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> ages = new HashMap<>();
        ages.put("Alice", 30);
        ages.put("Bob", 25);
        System.out.println(ages.get("Alice"));
    }
}

Den Schlüssel hashen

Wenn Sie put(key, value) aufrufen, ruft die Map key.hashCode() auf, um einen int zu erhalten.

HashMap verteilt diese Bits anschließend mit einer internen Funktion, damit sich auch schlechte Hash-Codes auf die Buckets verteilen.

Die endgültige Zahl wird mit hash & (table.length - 1) reduziert, um den Bucket-Index zu erhalten.
Die Tabellenlänge ist immer eine Zweierpotenz, daher funktioniert diese Maske.

public class Main {
    public static void main(String[] args) {
        String key = "Alice";
        int h = key.hashCode();
        int spread = h ^ (h >>> 16);
        int index = spread & (16 - 1);
        System.out.println("hashCode: " + h);
        System.out.println("bucket index: " + index);
    }
}

Buckets in Aktion

Jeder Bucket kann mehr als einen Eintrag enthalten. Wenn zwei Schlüssel auf denselben Bucket abgebildet werden, spricht man von einer Kollision.

Kollisionen sind normal und zu erwarten. HashMap behandelt sie, indem sie die Einträge im Bucket miteinander verkettet.

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<Integer, String> m = new HashMap<>();
        for (int i = 0; i < 5; i++) {
            m.put(i, "v" + i);
        }
        System.out.println(m.size() + " entries stored");
    }
}

Kollisionen und Verkettung

Vor Java 8 befanden sich alle kollidierenden Einträge in einer einfach verketteten Liste innerhalb des Buckets.

Beim Nachschlagen wird die Liste durchlaufen und equals() aufgerufen, bis der passende Schlüssel gefunden wird.

Wenige Kollisionen: weiterhin effektiv O(1).
Viele Kollisionen in einem Bucket: für diesen Bucket Annäherung an O(n).

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> m = new HashMap<>();
        m.put("FB", 1);
        m.put("Ea", 2);
        System.out.println("FB hash: " + "FB".hashCode());
        System.out.println("Ea hash: " + "Ea".hashCode());
        System.out.println(m.get("FB") + ", " + m.get("Ea"));
    }
}

Warum FB und Ea kollidieren

Die Strings "FB" und "Ea" haben in Java denselben hashCode(). Das ist ein klassisches Beispiel für eine Kollision.

Selbst bei identischen Hash-Codes hält die Map sie getrennt, weil equals() sie innerhalb des Buckets unterscheidet.

public class Main {
    public static void main(String[] args) {
        System.out.println("FB".hashCode() == "Ea".hashCode());
        System.out.println("FB".equals("Ea"));
    }
}

Lastfaktor

Der Lastfaktor legt fest, wie voll die Tabelle werden darf, bevor sie vergrößert wird. Der Standardwert ist 0.75.

Bei einer Kapazität von 16 und einem Lastfaktor von 0.75 wird die Größenänderung bei 12 Einträgen ausgelöst.
Ein niedrigerer Lastfaktor verbraucht mehr Speicher, reduziert aber Kollisionen.
Ein höherer Lastfaktor spart Speicher, erhöht jedoch die Anzahl der Kollisionen.

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<Integer, Integer> m = new HashMap<>(16, 0.75f);
        for (int i = 0; i < 12; i++) m.put(i, i);
        System.out.println("Stored " + m.size() + " entries");
    }
}

Die Tabelle vergrößern

Wenn die Anzahl der Einträge capacity * loadFactor überschreitet, wird die Tabelle verdoppelt.

Jeder vorhandene Eintrag wird in die neue, größere Tabelle neu gehasht. Das ist eine teure Operation, daher ist die Vorabdimensionierung bei großen Maps wichtig.

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        // Pre-size to avoid repeated resizes
        Map<Integer, Integer> m = new HashMap<>(1024);
        for (int i = 0; i < 800; i++) m.put(i, i * 2);
        System.out.println("size = " + m.size());
    }
}

Vorabdimensionierung für bessere Leistung

Wenn Sie ungefähr wissen, wie viele Einträge Sie speichern werden, geben Sie eine anfängliche Kapazität an, um häufige Größenänderungen zu vermeiden.

Faustregel: anfängliche Kapazität = expectedSize / 0.75 + 1.

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        int expected = 1000;
        int capacity = (int) (expected / 0.75) + 1;
        Map<Integer, String> m = new HashMap<>(capacity);
        System.out.println("Initial capacity hint: " + capacity);
        m.put(1, "ok");
        System.out.println(m.get(1));
    }
}

Null-Schlüssel und -Werte

HashMap erlaubt einen null-Schlüssel und mehrere null-Werte.

Der null-Schlüssel landet immer in Bucket 0 (sein Hash wird als 0 behandelt).
Verwenden Sie getOrDefault, um zwischen einem fehlenden Schlüssel und einem null-Wert unterscheiden zu können.

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, String> m = new HashMap<>();
        m.put(null, "nullKeyValue");
        m.put("a", null);
        System.out.println(m.get(null));
        System.out.println(m.getOrDefault("missing", "default"));
    }
}

Die Reihenfolge der Iteration ist nicht garantiert

HashMap macht keine Zusage über die Reihenfolge der Iteration. Die Reihenfolge hängt von den Hash-Codes und der Bucket-Anordnung ab.

Wenn Sie eine vorhersehbare Reihenfolge benötigen, verwenden Sie LinkedHashMap (Einfügereihenfolge) oder TreeMap (sortierte Reihenfolge).

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> m = new HashMap<>();
        m.put("one", 1);
        m.put("two", 2);
        m.put("three", 3);
        for (Map.Entry<String, Integer> e : m.entrySet()) {
            System.out.println(e.getKey() + "=" + e.getValue());
        }
    }
}

Der Pfad von get() zusammengefasst

Eine Suche läuft in folgenden Schritten ab:

hashCode() berechnen und die Bits verteilen.
Eine Maske anwenden, um den Bucket-Index zu ermitteln.
Den Bucket durchlaufen und die Schlüssel mit equals() vergleichen.
Den passenden Wert oder null zurückgeben.

Ein guter hashCode zusammen mit einem korrekten equals sorgt dafür, dass jeder Schritt schnell bleibt.

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> stock = new HashMap<>();
        stock.put("apple", 50);
        stock.put("pear", 20);
        String key = "apple";
        Integer qty = stock.get(key);
        System.out.println(key + " -> " + qty);
    }
}

Kurze Überprüfung

Testen Sie Ihr Verständnis davon, wie HashMap einen Bucket findet.

Zusammenfassung

Sie haben gelernt, wie HashMap intern funktioniert:

Schlüssel werden gehasht und Buckets zugeordnet.
Kollisionen werden behandelt, indem Einträge in einem Bucket verkettet werden.
Der Auslastungsfaktor (0.75) löst eine Verdopplung und ein erneutes Hashen aus.
Eine anfängliche Größenfestlegung vermeidet kostspielige Größenänderungen, und die Iterationsreihenfolge ist nicht garantiert.

Als Nächstes sehen Sie, warum hashCode allein ohne ein korrektes equals nicht ausreicht.

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> m = new HashMap<>(64);
        m.put("recap", 1);
        System.out.println("HashMap basics complete: " + m.get("recap"));
    }
}

Häufig gestellte Fragen

Ist die Lektion „Funktionsweise von HashMap“ kostenlos?

Ja — der vollständige Text von „Funktionsweise von HashMap“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Java Academy-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Java Academy-Kurs umfasst insgesamt 4 Lektionen.

Was lerne ich in „Funktionsweise von HashMap“?

Buckets, Hashing und Kollisionen Du übst Java Academy mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.

Brauche ich Erfahrung, um Java Academy zu starten?

Keine Vorkenntnisse erforderlich. Java Academy auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 1 von 4.

Wie lange dauert die Lektion „Funktionsweise von HashMap“?

Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.

Kann ich in dieser Java Academy-Lektion Code schreiben und ausführen?

Ja. Jede Java Academy-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.

Alle Lektionen in diesem Kurs

← Zurück zu Java Academy