TreeMap, SortedMap и NavigableMap в Java

Замените new HashMap<>() на new TreeMap<>(), чтобы ключи выводились по алфавиту, — и код, который годами работал, падает на map.put(null, 0) с NullPointerException. HashMap хранит null-ключ в отдельном бакете, а TreeMap должен сравнить ключ с другими через compareTo(), и для null это невозможно. Это не единственное различие: у отсортированной карты свои правила, свои исключения и набор методов поиска, которых у HashMap нет вовсе.

TreeMap — реализация интерфейса Map на основе красно-чёрного дерева, которая хранит пары «ключ–значение» отсортированными по ключу: в естественном порядке (Comparable) или по переданному Comparator. TreeMap реализует интерфейсы SortedMap (Java 1.2: первый/последний ключ, поддиапазоны) и NavigableMap (Java 6: поиск ближайшего ключа — floorKey(), ceilingKey(), lowerKey(), higherKey()). Операции get(), put(), remove() и containsKey() выполняются за O(log n).

Класс TreeMap: как устроен и как создать

TreeMap в Java хранит записи в узлах красно-чёрного дерева — самобалансирующегося двоичного дерева поиска, у которого высота всегда порядка log n. Поэтому поиск, вставка и удаление по ключу занимают O(log n), а обход карты всегда идёт по возрастанию ключей, независимо от порядка добавления.

Ключи сравниваются не через equals() и hashCode(), а через compareTo() или compare() компаратора: если сравнение вернуло 0, ключи считаются одинаковыми. Иерархия выглядит так:

Map<K,V>
└── SortedMap<K,V>        (Java 1.2; с Java 21 расширяет SequencedMap)
    └── NavigableMap<K,V>  (Java 6)
        ├── TreeMap<K,V>
        └── ConcurrentSkipListMap<K,V>  (потокобезопасная)

Базовые методы put(), get(), entrySet() и способы обхода общие для всех карт — они разобраны в уроке Интерфейс Map. Пример: зарплаты, добавленные не по алфавиту, TreeMap выводит отсортированными по фамилии:

import java.util.Map;
import java.util.TreeMap;

public class TreeMapExample {
    public static void main(String[] args) {
        Map<String, Double> salaries = new TreeMap<>();

        salaries.put("Петров", 123.22);
        salaries.put("Сидоров", 1378.00);
        salaries.put("Иванов", 3434.34);

        salaries.forEach((key, value) -> System.out.println(key + ": " + value));
    }
}

Вывод:

Иванов: 3434.34
Петров: 123.22
Сидоров: 1378.0

Строки сравниваются по кодам символов, поэтому кириллица сортируется по алфавиту, но все заглавные буквы идут раньше строчных (подробнее — в разделе Как compareTo сравнивает строки).

Конструкторы TreeMap

У TreeMap четыре конструктора: пустая карта с естественным порядком, пустая карта с компаратором и копирование из другой карты — обычной или отсортированной.

TreeMap с Comparator

Чтобы отсортировать TreeMap не в естественном порядке, в конструктор передают Comparator: например, Comparator.reverseOrder() для убывания или String.CASE_INSENSITIVE_ORDER для строк без учёта регистра. Компаратор определяет не только порядок обхода, но и то, какие ключи карта считает одинаковыми.

NavigableMap<Integer, String> desc = new TreeMap<>(Comparator.reverseOrder());
desc.put(1, "a");
desc.put(5, "e");
desc.put(3, "c");
System.out.println(desc);            // Вывод: {5=e, 3=c, 1=a}
System.out.println(desc.firstKey()); // Вывод: 5 — «первый» по правилу компаратора

Что выведет этот код?

import java.util.TreeMap;

public class CaseInsensitiveKeys {
    public static void main(String[] args) {
        TreeMap<String, Integer> map = new TreeMap<>(String.CASE_INSENSITIVE_ORDER);
        map.put("Java", 1);
        map.put("JAVA", 2);
        map.put("python", 3);

        System.out.println(map);
        System.out.println(map.get("jAvA"));
        System.out.println(map.containsKey("PYTHON"));
    }
}

Вывод:

{Java=2, python=3}
2
true

Компаратор вернул 0 для «Java» и «JAVA», поэтому второй put() не добавил новую запись, а заменил значение существующей. Ключ при этом остался прежним — «Java», а не «JAVA». Для словарей, логинов и HTTP-заголовков это удобно; для данных, где регистр важен, — источник тихой потери записей. Почему так происходит и как писать компаратор, согласованный с equals(), объясняет урок Comparable и Comparator.

Интерфейс SortedMap и его методы

SortedMap — интерфейс отсортированной карты: он гарантирует обход по возрастанию ключей и добавляет к Map методы для первого и последнего ключа и для вырезания поддиапазона ключей (headMap(), subMap(), tailMap()). Нижняя граница поддиапазона включается, верхняя — нет.

Пример: ключи добавлены в произвольном порядке, а методы SortedMap работают с ними как с отсортированным рядом 1, 2, 3, 4, 5, 100:

import java.util.SortedMap;
import java.util.TreeMap;

public class SortedMapExample {
    public static void main(String[] args) {
        SortedMap<Integer, Double> treeMap = new TreeMap<>();

        treeMap.put(3, 3434.34);
        treeMap.put(2, 1378.00);
        treeMap.put(1, 123.22);
        treeMap.put(4, 444.00);
        treeMap.put(5, 555.00);
        treeMap.put(100, 123.22);

        System.out.println("treeMap: " + treeMap);
        System.out.println("firstKey: " + treeMap.firstKey());
        System.out.println("lastKey: " + treeMap.lastKey());
        System.out.println("headMap(3): " + treeMap.headMap(3));
        System.out.println("subMap(3, 5): " + treeMap.subMap(3, 5));
        System.out.println("tailMap(4): " + treeMap.tailMap(4));
    }
}

Вывод:

treeMap: {1=123.22, 2=1378.0, 3=3434.34, 4=444.0, 5=555.0, 100=123.22}
firstKey: 1
lastKey: 100
headMap(3): {1=123.22, 2=1378.0}
subMap(3, 5): {3=3434.34, 4=444.0}
tailMap(4): {4=444.0, 5=555.0, 100=123.22}

headMap(3) вырезает начало карты до ключа 3, не включая его. subMap(3, 5) берёт середину: ключ 3 входит, ключ 5 — нет. tailMap(4) возвращает «хвост» от ключа 4 включительно до конца. Те же правила границ действуют для множеств — методы headSet(), subSet(), tailSet() из урока SortedSet и TreeSet.

headMap, subMap и tailMap — живые представления

Методы поддиапазонов не копируют данные: они возвращают представление (view) исходной карты. Изменения в исходной карте сразу видны в представлении и наоборот, а добавить в представление ключ за пределами его диапазона нельзя.

TreeMap<Integer, String> map = new TreeMap<>(Map.of(10, "десять", 20, "двадцать", 30, "тридцать"));
SortedMap<Integer, String> head = map.headMap(25);   // ключи меньше 25

map.put(15, "пятнадцать");     // добавили в исходную карту
System.out.println(head);

head.remove(10);               // удалили через представление
System.out.println(map);

head.put(40, "сорок");         // 40 вне диапазона < 25

Вывод:

{10=десять, 15=пятнадцать, 20=двадцать}
{15=пятнадцать, 20=двадцать, 30=тридцать}
Exception in thread "main" java.lang.IllegalArgumentException: key out of range

Если нужна независимая копия диапазона, оберните представление: new TreeMap<>(map.headMap(25)). Другие представления коллекций, включая Arrays.asList(), разобраны в уроке Backed Collections.

Интерфейс NavigableMap: поиск ближайших ключей

NavigableMap в Java — интерфейс, который расширяет SortedMap методами навигации: найти ближайший ключ меньше, не больше, не меньше или больше заданного, взять и удалить первую или последнюю запись, получить карту в обратном порядке и поддиапазоны с явными флагами включения границ. Появился в Java 6; реализуют его TreeMap и ConcurrentSkipListMap.

Главное отличие от get(): методы навигации не требуют точного совпадения ключа. Если ключа 35 нет, floorKey(35) вернёт ближайший ключ снизу, а не null.

Записи, которые возвращают firstEntry(), floorEntry() и другие *Entry-методы TreeMap, — неизменяемые снимки: вызов entry.setValue(...) бросит UnsupportedOperationException. Значение меняют через map.put(entry.getKey(), newValue).

Пример ниже показывает все четыре метода поиска на одной карте, в том числе для ключа 35, которого в карте нет, и для крайних ключей:

import java.util.NavigableMap;
import java.util.TreeMap;

public class NavigableMapExample {
    public static void main(String[] args) {
        NavigableMap<Integer, String> map = new TreeMap<>();
        map.put(30, "c");
        map.put(10, "a");
        map.put(50, "e");
        map.put(20, "b");
        map.put(40, "d");

        System.out.println("lowerKey(30) = " + map.lowerKey(30));
        System.out.println("floorKey(30) = " + map.floorKey(30));
        System.out.println("ceilingKey(30) = " + map.ceilingKey(30));
        System.out.println("higherKey(30) = " + map.higherKey(30));

        System.out.println("floorKey(35) = " + map.floorKey(35));
        System.out.println("ceilingKey(35) = " + map.ceilingKey(35));
        System.out.println("lowerKey(10) = " + map.lowerKey(10));
        System.out.println("higherKey(50) = " + map.higherKey(50));
        System.out.println("floorEntry(35) = " + map.floorEntry(35));
    }
}

Вывод:

lowerKey(30) = 20
floorKey(30) = 30
ceilingKey(30) = 30
higherKey(30) = 40
floorKey(35) = 30
ceilingKey(35) = 40
lowerKey(10) = null
higherKey(50) = null
floorEntry(35) = 30=c

Когда ключ есть в карте, floorKey() и ceilingKey() возвращают его самого, а lowerKey() и higherKey() — соседей. Когда ключа нет, строгие и нестрогие методы дают одинаковый результат. За пределами карты все четыре возвращают null, поэтому результат нужно проверять перед использованием. Те же методы для множеств называются lower(), floor(), ceiling(), higher() — урок NavigableSet.

Диапазоны и обратный порядок в NavigableMap

В NavigableMap у headMap(), tailMap() и subMap() есть перегрузки с флагами inclusive: true включает границу в результат, false исключает. Это снимает главное неудобство SortedMap, где верхняя граница всегда исключена. Для обхода от большего ключа к меньшему служит descendingMap().

Для той же карты {10=a, 20=b, 30=c, 40=d, 50=e}:

System.out.println(map.headMap(30));                    // {10=a, 20=b}
System.out.println(map.headMap(30, true));              // {10=a, 20=b, 30=c}
System.out.println(map.tailMap(30, false));             // {40=d, 50=e}
System.out.println(map.subMap(20, false, 40, true));    // {30=c, 40=d}
System.out.println(map.descendingMap());                // {50=e, 40=d, 30=c, 20=b, 10=a}
System.out.println(map.descendingKeySet());             // [50, 40, 30, 20, 10]

Методы pollFirstEntry() и pollLastEntry() превращают карту в очередь, отсортированную по ключу: каждый вызов возвращает крайнюю запись и удаляет её.

NavigableMap<Integer, String> queue = new TreeMap<>(map);

System.out.println("firstEntry: " + queue.firstEntry());
System.out.println("pollFirstEntry: " + queue.pollFirstEntry());
System.out.println("lastEntry: " + queue.lastEntry());
System.out.println("pollLastEntry: " + queue.pollLastEntry());
System.out.println("queue: " + queue);

Вывод:

firstEntry: 10=a
pollFirstEntry: 10=a
lastEntry: 50=e
pollLastEntry: 50=e
queue: {20=b, 30=c, 40=d}

firstEntry() и lastEntry() только читают крайние записи, а poll-методы возвращают те же записи и удаляют их, поэтому в итоговой карте нет ключей 10 и 50.

Практические примеры NavigableMap

NavigableMap удобна везде, где значение зависит от диапазона, в который попадает ключ: шкалы оценок и скидок, тарифы по весу или сумме, расписания по времени. Ключом служит нижняя граница диапазона, а нужный диапазон находит floorEntry() за O(log n) вместо цепочки if-else.

Шкала оценок через floorEntry

import java.util.NavigableMap;
import java.util.TreeMap;

public class GradeScale {
    public static void main(String[] args) {
        NavigableMap<Integer, String> grades = new TreeMap<>();
        grades.put(0, "неудовлетворительно");
        grades.put(60, "удовлетворительно");
        grades.put(75, "хорошо");
        grades.put(90, "отлично");

        for (int score : new int[]{95, 75, 74, 12}) {
            System.out.println(score + " -> " + grades.floorEntry(score).getValue());
        }
    }
}

Вывод:

95 -> отлично
75 -> хорошо
74 -> удовлетворительно
12 -> неудовлетворительно

Для 75 floorEntry() находит точное совпадение, для 74 — ближайшую границу снизу, 60. А для отрицательного балла, например -5, ключа ≤ -5 в карте нет: floorEntry(-5) вернёт null, и getValue() бросит NullPointerException. Поэтому шкала должна начинаться с минимально возможного значения, или результат нужно проверять на null.

Расписание: события в интервале времени

import java.time.LocalTime;
import java.util.NavigableMap;
import java.util.TreeMap;

public class Schedule {
    public static void main(String[] args) {
        NavigableMap<LocalTime, String> schedule = new TreeMap<>();
        schedule.put(LocalTime.of(9, 0), "Планёрка");
        schedule.put(LocalTime.of(10, 30), "Код-ревью");
        schedule.put(LocalTime.of(13, 0), "Обед");
        schedule.put(LocalTime.of(15, 0), "Демо");
        schedule.put(LocalTime.of(17, 30), "Ретро");

        LocalTime now = LocalTime.of(12, 0);
        System.out.println("С 10:00 до 15:00: "
                + schedule.subMap(LocalTime.of(10, 0), true, LocalTime.of(15, 0), true));
        System.out.println("Следующее: " + schedule.ceilingEntry(now));
        System.out.println("Предыдущее: " + schedule.lowerEntry(now));
    }
}

Вывод:

С 10:00 до 15:00: {10:30=Код-ревью, 13:00=Обед, 15:00=Демо}
Следующее: 13:00=Обед
Предыдущее: 10:30=Код-ревью

LocalTime реализует Comparable, поэтому компаратор не нужен. Флаг true у верхней границы включил событие ровно в 15:00 — с subMap(from, to) из SortedMap «Демо» в результат бы не попало.

TreeMap vs HashMap: что выбрать

HashMap выбирают по умолчанию: операции в среднем O(1), но порядок ключей не гарантирован. TreeMap медленнее — O(log n) на операцию, — зато хранит ключи отсортированными, умеет искать ближайший ключ и вырезать диапазоны. Если нужен только порядок добавления, а не сортировка, подходит LinkedHashMap.

Почему HashMap работает за O(1) и что происходит при коллизиях, разобрано в уроке HashMap: как устроена внутри, а сводная таблица всех реализаций Map — в уроке Интерфейс Map. Частый приём: собрать данные в HashMap, а отсортировать один раз перед выводом — new TreeMap<>(hashMap).

На чём чаще всего ошибаются

Большинство ошибок с TreeMap связаны с тем, что ключи сравниваются через compareTo()/compare(), а не через equals(), и с тем, что границы диапазонов включаются по-разному. Типичные промахи и их исправления: