Java Academy · Lektion

Treeification und Performance

Wie Java 8+ Kollisionen behandelt

Treeification und Performance ist eine kostenlose Java Academy-Lektion auf CoddyKit. Dies ist Lektion 4 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.

Das Kollisionsproblem

Vor Java 8 wurde ein Bucket mit vielen Kollisionen zu einer langen verketteten Liste. Die Suche in diesem Bucket verschlechterte sich auf O(n).

Ein Angreifer konnte dies mit präparierten Schlüsseln für einen Denial-of-Service-Angriff ausnutzen, indem alle Schlüssel in einem Bucket landeten.

public class Main {
    public static void main(String[] args) {
        // All these strings can be made to collide in one bucket
        System.out.println("FB".hashCode() == "Ea".hashCode());
    }
}

Treeification in Java 8

Java 8 führte die Treeification ein. Wenn ein einzelner Bucket zu viele Einträge enthält, wird die verkettete Liste in einen balancierten Rot-Schwarz-Baum umgewandelt.

Die Suche in diesem Bucket benötigt dann O(log n) statt O(n).

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

public class Main {
    public static void main(String[] args) {
        Map<Integer, Integer> m = new HashMap<>();
        for (int i = 0; i < 1000; i++) m.put(i, i);
        System.out.println("Lookups stay fast: " + m.get(742));
    }
}

Der Schwellenwert: TREEIFY_THRESHOLD

Die Konstante TREEIFY_THRESHOLD ist 8. Ein Bucket wird in einen Baum umgewandelt, sobald er 8 Einträge erreicht.

Es gibt jedoch eine zweite Bedingung: Die Tabelle muss außerdem mindestens die Größe MIN_TREEIFY_CAPACITY (64) haben, sonst wird die Map stattdessen vergrößert.

public class Main {
    public static void main(String[] args) {
        int TREEIFY_THRESHOLD = 8;
        int MIN_TREEIFY_CAPACITY = 64;
        System.out.println("Treeify when bucket size >= " + TREEIFY_THRESHOLD);
        System.out.println("...and table capacity >= " + MIN_TREEIFY_CAPACITY);
    }
}

Zuerst vergrößern, später Treeification

Wenn ein Bucket überläuft, die Tabelle aber noch klein ist (unter 64), vergrößert HashMap zunächst die Tabelle.

Durch die Größenänderung werden die Einträge normalerweise neu verteilt und der Hotspot beseitigt. Daher ist Treeification nur das letzte Mittel bei tatsächlich schlechter Hashverteilung.

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

public class Main {
    public static void main(String[] args) {
        Map<Integer, Integer> m = new HashMap<>(16);
        for (int i = 0; i < 50; i++) m.put(i, i);
        // Many resizes happened before any treeify would
        System.out.println("size = " + m.size());
    }
}

Untreeification

Bäume sind nicht dauerhaft. Wenn Löschvorgänge einen Bucket unter UNTREEIFY_THRESHOLD (6) verkleinern, wird der Baum wieder in eine verkettete Liste umgewandelt.

Der Abstand zwischen 8 (Treeification) und 6 (Untreeification) verhindert ein ständiges Hin- und Herwechseln an der Grenze.

public class Main {
    public static void main(String[] args) {
        System.out.println("TREEIFY_THRESHOLD   = 8");
        System.out.println("UNTREEIFY_THRESHOLD = 6");
        System.out.println("Gap prevents flip-flopping at the edge");
    }
}

Bäume benötigen Comparable oder eine Identitätsreihenfolge

Ein Rot-Schwarz-Baum muss seine Einträge ordnen. HashMap vergleicht zunächst die Hashcodes. Bei Gleichstand wird Comparable verwendet, wenn die Schlüssel diesen Typ implementieren, andernfalls eine stabile Tie-Break-Regel anhand von Klassennamen und Identität.

Schlüssel, die Comparable sind (wie String oder Integer), ermöglichen die sauberste Baumordnung.

public class Main {
    public static void main(String[] args) {
        System.out.println("String is Comparable: " + ("a" instanceof Comparable));
        System.out.println("Integer is Comparable: " + (Integer.valueOf(1) instanceof Comparable));
    }
}

Praktische Auswirkungen

Bei den meisten realen Programmen mit guten Hashcodes werden Sie niemals Treeification beobachten. Die Buckets bleiben kurz.

Treeification ist ein Sicherheitsnetz, das die Suche im schlechtesten Fall selbst bei schlechter oder absichtlich herbeigeführter Hashverteilung auf O(log n) begrenzt.

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("alpha", 1);
        m.put("beta", 2);
        m.put("gamma", 3);
        // Tiny buckets, plain linked lists, no trees needed
        System.out.println(m.get("beta"));
    }
}

Ein konstanter hashCode erzwingt Treeification

Wenn Sie absichtlich einen konstanten hashCode zurückgeben, landet jeder Schlüssel in einem Bucket. Bei einer Kapazität von mindestens 64 wird dieser Bucket in einen Baum umgewandelt.

Das demonstriert das Sicherheitsnetz, ist aber ein schlechtes Design. Korrigieren Sie stattdessen den hashCode.

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

public class Main {
    static class Bad implements Comparable<Bad> {
        final int v;
        Bad(int v) { this.v = v; }
        @Override public int hashCode() { return 1; } // forces collisions
        @Override public boolean equals(Object o) { return o instanceof Bad b && b.v == v; }
        @Override public int compareTo(Bad o) { return Integer.compare(v, o.v); }
    }
    public static void main(String[] args) {
        Map<Bad, Integer> m = new HashMap<>();
        for (int i = 0; i < 100; i++) m.put(new Bad(i), i);
        System.out.println("All in one bucket, still works: " + m.get(new Bad(50)));
    }
}

Speicherkosten von Bäumen

Baumknoten sind größer als einfache Knoten verketteter Listen, weil sie Referenzen auf Elternknoten, linke und rechte Kindknoten sowie die Farbe speichern.

Das ist ein weiterer Grund dafür, dass Treeification ein Fallback und nicht der Standard ist: Bäume tauschen Speicher gegen Geschwindigkeit im schlechtesten Fall.

public class Main {
    public static void main(String[] args) {
        System.out.println("Node: hash, key, value, next");
        System.out.println("TreeNode: + parent, left, right, prev, red flag");
        System.out.println("=> trees cost more memory per entry");
    }
}

So vermeiden Sie Treeification

Sie sollten sich fast nie auf Treeification verlassen. Vermeiden Sie sie durch:

Schreiben eines gut verteilten hashCode().
Verwenden integrierter Typen oder Records als Schlüssel.
Festlegen der anfänglichen Map-Größe, um Kollisionen zu reduzieren.

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

public class Main {
    record Key(int a, int b) {}
    public static void main(String[] args) {
        Map<Key, Integer> m = new HashMap<>(256);
        for (int i = 0; i < 200; i++) m.put(new Key(i, i * 31), i);
        System.out.println("Even distribution, fast lookups: " + m.get(new Key(10, 310)));
    }
}

Zusammenfassung der Performance

Kosten von HashMap-Operationen:

Guter Hash: durchschnittlich O(1).
Verketteter Bucket: im schlechtesten Fall O(n) pro Bucket.
Treeifizierter Bucket: O(log n) pro Bucket.

Treeification begrenzt den schlechtesten Fall, aber ein guter hashCode hält Sie im Bereich O(1).

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

public class Main {
    public static void main(String[] args) {
        Map<Integer, Integer> m = new HashMap<>(1 << 14);
        for (int i = 0; i < 10000; i++) m.put(i, i);
        System.out.println("10k entries, O(1) get: " + m.get(9999));
    }
}

Kurze Überprüfung

Testen Sie Ihr Wissen über Treeification.

Zusammenfassung

Sie haben gelernt, wie moderne HashMap Kollisionen behandelt:

Buckets werden ab 8 Einträgen treeifiziert, wenn die Kapazität mindestens 64 beträgt.
Bäume ermöglichen eine Suche im schlechtesten Fall mit O(log n).
Buckets werden bei weniger als 6 Einträgen wieder in Listen umgewandelt.
Ein guter hashCode sorgt dafür, dass dieses Sicherheitsnetz nur selten ausgelöst wird.

Sie haben den Kurs zu den Interna von HashMap abgeschlossen.

public class Main {
    public static void main(String[] args) {
        System.out.println("Treeification course complete");
    }
}

Häufig gestellte Fragen

Ist die Lektion „Treeification und Performance“ kostenlos?

Ja — der vollständige Text von „Treeification und Performance“ 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 „Treeification und Performance“?

Wie Java 8+ Kollisionen behandelt 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 4 von 4.

Wie lange dauert die Lektion „Treeification und Performance“?

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