Класс Java TreeMap | W3Docs Learn Java

Что такое TreeMap

TreeMap<K, V> — это реализация Map, которая хранит ключи в отсортированном порядке. Внутри это красно-чёрное дерево — то же самобалансирующееся бинарное дерево поиска, что и в TreeSet — и каждая операция выполняется за O(log n): put, get, remove, первый ключ, последний ключ, диапазонные запросы. Платой за логарифмическую стоимость является навигационный API интерфейса NavigableMap<K, V>: floor, ceiling, lower, higher, sub-map, head-map, tail-map, обратные представления. Ничего из этого невозможно получить от хеш-таблицы без полной сортировки.

Если вы когда-либо делаете new TreeMap<>(hashMap) в конце функции, чтобы «отсортировать записи» — это сигнал, что TreeMap должен был быть типом с самого начала.

Два способа определить порядок ключей

TreeMap нужно как-то сравнивать ключи. Как и у TreeSet:

Естественный порядок — тип ключа реализует Comparable<K>. String, числовые обёртки, даты и ваши собственные типы record, реализующие Comparable, подходят.
Comparator<K>, переданный в конструктор — используйте его, когда естественный порядок отсутствует или не подходит. (См. Comparable vs Comparator о том, чем они отличаются.)

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());

Как и у TreeSet, равенство определяется по возврату 0 из compareTo, а не по equals. Два ключа, которые компаратор считает равными, сливаются в одну запись — второй put перезаписывает первый. При использовании ключей с String.CASE_INSENSITIVE_ORDER, если добавить "Java", а затем "JAVA", останется одна запись с исходным ключом "Java" и значением второго put. Почти никогда это не то, что вы хотите получить случайно.

API NavigableMap

Интерфейс, реализуемый TreeMap, предоставляет гораздо больше операций, чем обычный Map:

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

Именно для этого и существует TreeMap. «Найти ближайшее событие до 9 утра» — это headMap(9am).lastEntry() — один поиск за логарифмическое время. Та же операция над HashMap потребовала бы перебора каждого ключа.

Представления sub-map являются живыми

subMap, headMap и tailMap возвращают представления исходной карты — не копии. Изменения, сделанные через представление, передаются обратно, а изменения оригинала, попадающие в диапазон представления, отображаются в нём. Представления также применяют ограничение диапазона: попытка добавить ключ вне диапазона через представление бросит IllegalArgumentException. Именно так диапазонная итерация остаётся безопасной даже при изменениях во время обхода.

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 для ключей не допускается

В TreeMap нельзя использовать null в качестве ключа по той же причине, по которой TreeSet их отвергает: нет разумного способа вызвать compareTo на null. Первый put(null, ...) бросит NullPointerException. Null-значения допустимы.

Когда выбирать `TreeMap`

Дерево принятия решений:

Нужна сортированная итерация по ключу или диапазонные запросы по ключам → TreeMap. Единственный выбор.
Нужен быстрый поиск, порядок не важен → HashMap. O(1) побеждает.
Нужен быстрый поиск и итерация в порядке вставки → LinkedHashMap.
Тип ключа — перечисление → EnumMap. Быстрее TreeMap и упорядочен естественным образом.

Все четыре реализуют один и тот же контракт Map, поэтому переключение между ними обычно является изменением конструктора в одну строку.

Полезный паттерн: используйте HashMap для быстрого построения карты, а затем new TreeMap<>(hashMap) один раз для отсортированного представления в конце. Строить быстро, представлять отсортированно.

Рабочий пример: поиск в расписании, диапазонные запросы, ключи с компаратором

Программа ниже использует TreeMap для моделирования небольшого «расписания событий» с ключами в виде минут с полуночи. Она демонстрирует навигационный API для «какое следующее событие после X» и «всё до Y», показывает живое представление sub-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);
  }
}

Что можно извлечь из выполнения:

Расписание выводится в хронологическом порядке без какой-либо явной сортировки. Добавление "coffee" в 11:30 автоматически поместило его на нужное место.
Запрос на 11:00. ceilingEntry(11*60) возвращает следующую запись в 11:00 или позже — это обед в 13:00 (обзор дизайна в 10:30 до 11:00, поэтому не подходит). lowerEntry(11*60) возвращает последнюю запись строго до 11:00 — обзор дизайна в 10:30. Оба запроса выполняются за O(log n).
Под-карта morning является живым представлением — coffee появился в ней после добавления в исходную карту. Если бы мы добавили "midnight snack" в 23:00, представление проигнорировало бы его (вне диапазона).
pollFirstEntry последовательно извлекал следующее событие. Это бедняцкая очередь с приоритетом, когда нужен также поиск по ключу, что настоящий PriorityQueue дать не может.
Карта без учёта регистра объединила "Java" и "JAVA" в одну запись — с ключом исходного "Java", но значением второго put равным 2. Равенство через компаратор, а не через equals.

Что дальше

Четыре современные реализации карт — HashMap, LinkedHashMap, TreeMap и ConcurrentHashMap — это те, к которым стоит обращаться в новом коде. В JDK есть ещё одна, предшествующая им всем, которую вы иногда встретите в старом коде: Hashtable. Стоит знать, зачем она существует, почему сегодня она почти всегда является неверным выбором, и как её заменить.

Практика

В `TreeMap<Integer, String>` содержатся ключи `10, 20, 30, 40`. Что вернёт `tree.floorKey(25)`?

`20` — наибольший ключ, меньший или равный 25`30` — наименьший ключ, больший или равный 25`25` — ключ вставляется со значением null и возвращается`null` — `floorKey` возвращает ключ только при точном совпадении в карте