Java TreeMap-Klasse | W3Docs Learn Java

Was eine TreeMap ist

TreeMap<K, V> ist die Map, die ihre Schlüssel sortiert hält. Intern verwendet sie einen Rot-Schwarz-Baum — denselben selbstbalancierenden binären Suchbaum, der auch TreeSet zugrunde liegt — und jede Operation ist O(log n): put, get, remove, der erste Schlüssel, der letzte Schlüssel, Bereichsabfragen. Der Preis für die logarithmische Komplexität ist die Navigations-API auf NavigableMap<K, V>: floor, ceiling, lower, higher, sub-map, head-map, tail-map, absteigende Ansichten. Nichts davon ist bei einer Hash-Tabelle ohne vollständiges Sortieren möglich.

Wenn Sie sich dabei ertappen, am Ende einer Funktion new TreeMap<>(hashMap) zu schreiben, um "die Einträge zu sortieren," ist das das Signal, dass TreeMap von Anfang an der richtige Typ gewesen wäre.

Zwei Arten, die Schlüsselreihenfolge festzulegen

Eine TreeMap muss Schlüssel irgendwie vergleichen. Wie bei TreeSet gibt es dafür zwei Möglichkeiten:

Natürliche Ordnung — der Schlüsseltyp implementiert Comparable<K>. Strings, numerische Wrapper, Datumstypen und eigene record-Typen, die Comparable implementieren, kommen alle infrage.
Ein Comparator<K>, der dem Konstruktor übergeben wird — verwenden Sie ihn, wenn keine natürliche Ordnung vorhanden ist oder diese nicht Ihren Anforderungen entspricht. (Siehe Comparable vs Comparator für die Unterschiede zwischen beiden.)

Map<String, Integer> byName    = new TreeMap<>();                        // case-sensitive natural
Map<String, Integer> byNameCi  = new TreeMap<>(String.CASE_INSENSITIVE_ORDER);
Map<String, Integer> reverse   = new TreeMap<>(Comparator.reverseOrder());

Wie bei TreeSet gilt: Gleichheit wird über compareTo mit Rückgabewert 0 bestimmt, nicht über equals. Zwei Schlüssel, die der Comparator als gleich einstuft, kollabieren zu einem einzigen Eintrag — das zweite put überschreibt das erste. Bei einer String.CASE_INSENSITIVE_ORDER-Schlüsselung führt das Einsetzen von "Java" und anschließend "JAVA" zu einem einzigen Eintrag, dessen Schlüssel das ursprüngliche "Java" ist und dessen Wert der Wert des zweiten put ist. Das ist fast nie das, was man aus Versehen möchte.

Die NavigableMap-API

Die Schnittstelle, die eine TreeMap implementiert, bietet Ihnen viele Operationen, die eine einfache Map nicht bietet:

TreeMap<Integer, String> t = new TreeMap<>();
t.put(10, "a"); t.put(20, "b"); t.put(30, "c"); t.put(40, "d");

t.firstKey();        // 10
t.lastKey();         // 40
t.firstEntry();      // 10=a
t.pollFirstEntry();  // 10=a, removes
t.lowerKey(30);      // 20 — strictly less
t.floorKey(30);      // 30 — ≤
t.higherKey(30);     // 40 — strictly greater
t.ceilingKey(30);    // 30 — ≥
t.headMap(30);       // {10=a, 20=b}  — keys strictly < 30
t.tailMap(30);       // {30=c, 40=d}  — keys ≥ 30
t.subMap(20, 40);    // {20=b, 30=c}  — [20, 40)
t.descendingMap();   // reverse-order view

Das ist der Grund, warum TreeMap existiert. "Finde das nächste Ereignis vor 9 Uhr" lautet headMap(9am).lastEntry() — eine logarithmische Suche. Dieselbe Operation auf einer HashMap müsste jeden Schlüssel durchsuchen.

Sub-Map-Ansichten sind live

subMap, headMap und tailMap geben Ansichten der ursprünglichen Map zurück — keine Kopien. Änderungen, die über die Ansicht vorgenommen werden, wirken sich auf die ursprüngliche Map aus, und Änderungen an der ursprünglichen Map, die in den Bereich der Ansicht fallen, erscheinen in der Ansicht. Die Ansichten erzwingen auch den Bereich: Der Versuch, über die Ansicht einen Schlüssel außerhalb des Bereichs einzufügen, löst IllegalArgumentException aus. So bleibt die bereichsbegrenzte Iteration auch bei Mutationen während des Durchlaufs sicher.

TreeMap<Integer, String> t = new TreeMap<>();
t.put(10, "a"); t.put(20, "b"); t.put(30, "c");
NavigableMap<Integer, String> mid = t.subMap(15, true, 25, true);
mid.put(20, "updated");   // OK — 20 is in range
// mid.put(40, "x");       // would throw — 40 is out of range
System.out.println(t);     // {10=a, 20=updated, 30=c}

Null wird (bei Schlüsseln) abgelehnt

In einer TreeMap kann kein null-Schlüssel vorhanden sein, aus demselben Grund, warum TreeSet sie ablehnt: Es gibt keine sinnvolle Möglichkeit, compareTo auf null aufzurufen. Das erste put(null, ...) löst NullPointerException aus. Null-Werte sind jedoch zulässig.

Wann man `TreeMap` wählt

Entscheidungsablauf:

Sie benötigen sortierte Iteration nach Schlüssel oder Bereichsabfragen auf Schlüsseln → TreeMap. Die einzige Wahl.
Sie benötigen schnellen Zugriff und Reihenfolge ist egal → HashMap. O(1) gewinnt.
Sie benötigen schnellen Zugriff und Iteration in Einfügereihenfolge → LinkedHashMap.
Der Schlüsseltyp ist ein Enum → EnumMap. Schneller als TreeMap und von Natur aus geordnet.

Alle vier implementieren denselben Map-Vertrag, sodass der Wechsel zwischen ihnen in der Regel eine einzeilige Konstruktoränderung ist.

Ein nützliches Muster: Verwenden Sie eine HashMap zum schnellen Aufbau der Map und dann einmalig new TreeMap<>(hashMap), um am Ende eine sortierte Ansicht darzustellen. Schnell aufbauen, sortiert präsentieren.

Ein ausgearbeitetes Beispiel: Terminplanung, Bereichsabfragen, Comparator-Schlüsselung

Das folgende Programm verwendet eine TreeMap, um einen kleinen "Terminplan" zu modellieren, der nach Minuten seit Mitternacht als Schlüssel geordnet ist. Es demonstriert die Navigations-API für "was ist das nächste Ereignis nach X" und "alles vor Y," zeigt die live Sub-Map-Ansicht und enthüllt die Comparator-Gleichheitsfalle mit einer case-insensitiven Map.

java— editable, runs on the server

import java.util.*;

public class TreeMapShowcase {
  public static void main(String[] args) {
    // --- A schedule keyed by minutes-since-midnight ---
    TreeMap<Integer, String> schedule = new TreeMap<>();
    schedule.put( 9 * 60,     "standup");
    schedule.put(10 * 60 + 30, "design review");
    schedule.put(13 * 60,     "lunch with team");
    schedule.put(16 * 60,     "demo");
    schedule.put(18 * 60,     "ship");
    System.out.println("schedule (sorted by key):");
    schedule.forEach((k, v) ->
        System.out.println("  " + (k / 60) + ":" + String.format("%02d", k % 60) + "  " + v));

int now = 11 * 60 + 0;
    System.out.println("\nat 11:00...");
    System.out.println("  next event:           " + schedule.ceilingEntry(now));
    System.out.println("  most recent past:     " + schedule.lowerEntry(now));

// --- Morning slice: live view ---
    NavigableMap<Integer, String> morning = schedule.headMap(12 * 60, false);
    System.out.println("\nmorning (key < 12:00):  " + morning);
    schedule.put(11 * 60 + 30, "coffee");      // falls in the morning range
    System.out.println("after adding coffee at 11:30:");
    System.out.println("  morning view:  " + morning);  // reflects the new entry

// --- pollFirstEntry: priority-queue-like draining ---
    System.out.println("\ndraining in time order:");
    while (!schedule.isEmpty()) {
      Map.Entry<Integer, String> next = schedule.pollFirstEntry();
      System.out.println("  " + (next.getKey() / 60) + ":"
          + String.format("%02d", next.getKey() % 60) + "  " + next.getValue());
    }

// --- The comparator-equality trap ---
    TreeMap<String, Integer> ci = new TreeMap<>(String.CASE_INSENSITIVE_ORDER);
    ci.put("Java", 1);
    ci.put("JAVA", 2);     // comparator says equal → overwrites value, keeps original key
    System.out.println("\ncase-insensitive: " + ci);
  }
}

Was man aus dem Durchlauf mitnehmen sollte:

Der Terminplan wird in chronologischer Reihenfolge ausgegeben, ohne explizite Sortierung. Das Hinzufügen von "coffee" um 11:30 Uhr ordnete es automatisch an der richtigen Stelle ein.
Wir haben zum Zeitpunkt 11:00 Uhr abgefragt. ceilingEntry(11*60) gibt den nächsten Eintrag bei oder nach 11:00 Uhr zurück, das ist das Mittagessen um 13:00 Uhr (das Design-Review um 10:30 Uhr liegt vor 11:00 Uhr und kommt daher nicht infrage). lowerEntry(11*60) gibt den jüngsten Eintrag strikt vor 11:00 Uhr zurück, das Design-Review um 10:30 Uhr. Beide sind O(log n).
Die morning-Sub-Map ist eine live-Ansicht — coffee erschien darin, nachdem wir es in die ursprüngliche Map eingefügt hatten. Hätten wir "midnight snack" um 23:00 Uhr eingefügt, hätte die Ansicht diesen ignoriert (außerhalb des Bereichs).
pollFirstEntry hat wiederholt das nächste anstehende Ereignis entnommen. Das ist eine einfache Prioritätswarteschlange, wenn man auch Lookups nach Schlüssel benötigt, was eine echte PriorityQueue nicht leisten kann.
Die case-insensitive Map kollabierte "Java" und "JAVA" zu einem einzigen Eintrag — mit dem ursprünglichen Schlüssel "Java", aber dem Wert des zweiten puts 2. Comparator-Gleichheit, nicht equals-Gleichheit.

Was als Nächstes kommt

Die vier modernen Map-Implementierungen — HashMap, LinkedHashMap, TreeMap und ConcurrentHashMap — sind die zu bevorzugenden in neuem Code. Es gibt noch eine weitere im JDK, die all diesen vorausgeht und gelegentlich in altem Code zu sehen ist: Hashtable. Es lohnt sich zu wissen, warum sie existiert, warum sie heute fast immer die falsche Wahl ist und wie man sie ersetzen kann.

Übungen

Übung

Eine `TreeMap<Integer, String>` enthält die Schlüssel `10, 20, 30, 40`. Was gibt `tree.floorKey(25)` zurück?

`20` — der größte Schlüssel, der kleiner oder gleich 25 ist`30` — der kleinste Schlüssel, der größer oder gleich 25 ist`25` — der Schlüssel wird mit einem null-Wert eingefügt und zurückgegeben`null` — `floorKey` gibt nur einen Schlüssel zurück, wenn er exakt in der Map vorhanden ist