Java TreeMap — обзор и примеры

Дерево с зелёными листьями

Что такое TreeMap

TreeMap — это реализация интерфейса Map, основанная на структуре данных “красно‑чёрное дерево”. Она хранит пары ключ‑значение и автоматически поддерживает порядок по ключам. Типы ключей и значений задаются через параметризованные типы (generics): первый параметр — тип ключа, второй — тип значения.

Краткое определение терминов:

Map: коллекция пар “ключ→значение” с быстрым доступом по ключу.
Красно‑чёрное дерево: самобалансирующееся бинарное дерево поиска, обеспечивающее O(log n) для основных операций.

Как создать TreeMap в Java

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

// Создать новую пустую TreeMap
TreeMap customers = new TreeMap();

Конструкторы также позволяют задать Comparator для пользовательского порядка или инициализировать TreeMap из другой карты.

Заполнение TreeMap

Метод put() добавляет пару ключ‑значение. Порядок вставки не важен: структура хранит элементы в порядке ключей.

// Заполнить TreeMap
customers.put(105, "Jessica Jones");
customers.put(102, "Mark Williams");
customers.put(104, "Phil Blair");
customers.put(101, "Kim Brown");
customers.put(103, "Jim Riley");

После вставки элементы в customers будут упорядочены по ключу.

Просмотр элементов

Чтобы увидеть все пары, достаточно распечатать объект TreeMap:

// Показать всё содержимое TreeMap
System.out.println(customers);

Вывод будет выглядеть так:

{101=Kim Brown, 102=Mark Williams, 103=Jim Riley, 104=Phil Blair, 105=Jessica Jones}

Для построчного вывода можно пройти по entrySet():

// Итерация по элементам
for (Map.Entry customer : customers.entrySet()) {
    System.out.println("Key: " + customer.getKey() + " Value: " + customer.getValue());
}

Результат:

Key: 101 Value: Kim Brown
Key: 102 Value: Mark Williams
Key: 103 Value: Jim Riley
Key: 104 Value: Phil Blair
Key: 105 Value: Jessica Jones

Обновление элементов

Для изменения значения используется метод replace(). Есть две перегрузки: одна принимает ключ и новое значение, другая — ключ, старое значение и новое значение (меняет только если текущее совпадает с ожидаемым).

// Заменить значение по ключу
customers.replace(101, "Kim Smith");
System.out.println(customers);

Вывод:

{101=Kim Smith, 102=Mark Williams, 103=Jim Riley, 104=Phil Blair, 105=Jessica Jones}

Другой пример:

// Условная замена
customers.replace(103, "Jim Riley", "Michelle Noah");
System.out.println(customers);

Вывод:

{101=Kim Brown, 102=Mark Williams, 103=Michelle Noah, 104=Phil Blair, 105=Jessica Jones}

Удаление элементов

Метод remove(key) удаляет элемент по ключу и возвращает удалённое значение. Метод clear() очищает всю карту.

// Удалить по ключу
customers.remove(104);
System.out.println(customers);

Вывод после удаления:

{101=Kim Smith, 102=Mark Williams, 103=Michelle Noah, 105=Jessica Jones}

TreeMap и HashMap — сравнение

Обе реализуют Map и унаследованы от AbstractMap, но различаются реализациями и поведением:

TreeMap использует красно‑чёрное дерево и поддерживает упорядоченность по ключам (возрастающий порядок по умолчанию).
HashMap использует хеш‑таблицу и не гарантирует порядка.
HashMap допускает один null‑ключ; TreeMap не допускает null в ключах (может бросать NullPointerException при попытке вставить null‑ключ).
По скорости доступа HashMap быстрее в среднем (O(1) амортизированно), TreeMap даёт O(log n) для вставки, удаления и поиска.

Выбор зависит от требований: нужен ли упорядоченный проход или быстрый произвольный доступ.

Когда использовать TreeMap

Нужен обход элементов в отсортированном порядке.
Требуются операции диапазона: subMap(), headMap(), tailMap().
Необходимо получить ближайшие ключи (ceilingKey, floorKey, higherKey, lowerKey).

Когда TreeMap не подходит

Когда важна максимальная производительность доступа по ключу и порядок не нужен — лучше HashMap.
Когда ключи могут быть null — HashMap позволяет null‑ключ (один), TreeMap — нет.
Для многопоточной записи/чтения из разных потоков используйте ConcurrentHashMap или ConcurrentSkipListMap.

Альтернативы в стандартной библиотеке

HashMap — быстрая хеш‑реализация, неупорядоченная.
LinkedHashMap — сохраняет порядок вставки, полезен для кэшей LRU при ограниченном размере.
ConcurrentSkipListMap — потокобезопасная упорядоченная реализация на основе пропускающих списков.

Полезные методы TreeMap

put(K, V)
get(K)
remove(K)
replace(K, V) и replace(K, oldV, newV)
firstKey(), lastKey()
ceilingKey(K), floorKey(K), higherKey(K), lowerKey(K)
subMap(fromKey, toKey), headMap(toKey), tailMap(fromKey)

Быстрая шпаргалка по сложности

Вставка: O(log n)
Поиск: O(log n)
Удаление: O(log n)
Обход элементов: O(n)

Пример поведения при диапазонном запросе

// Получить клиентов с ключами от 102 (включительно) до 104 (исключительно)
SortedMap range = customers.subMap(102, 104);
System.out.println(range);

Факто‑бокс

Количество конструкторов: 4
Порядок: сортировка по ключам (по Comparable или Comparator)
Null‑ключи: не поддерживает
Основная структура: красно‑чёрное дерево
Сложность операций: O(log n)

Критерии приёмки

TreeMap корректно сортирует элементы по ключам.
Методы put/get/remove работают с ожидаемой логарифмической сложностью (функциональные тесты).
subMap/headMap/tailMap возвращают нужные диапазоны.
При попытке вставить null в ключ — приложение ожидаемо обрабатывает исключение.

Контрольный чеклист перед выбором TreeMap

Нужен упорядоченный перебор по ключам? Да / Нет
Требуются диапазонные запросы? Да / Нет
Ключи могут быть null? Если да — подумать об альтернативе
Нужна потокобезопасность? Если да — использовать ConcurrentSkipListMap или внешнюю синхронизацию

Примеры отказов и ограничений

Платформа с большим объёмом операций записи и строгими требованиями к задержкам: HashMap обычно даст лучшую производительность.
Если требуется сохранять порядок вставки, а не сортировку ключей — LinkedHashMap предпочтительнее.

Модель принятия решения (пример)

flowchart TD
  A[Нужен упорядоченный доступ?] -->|Да| B{Нужна потокобезопасность?}
  A -->|Нет| C[Используйте HashMap]
  B -->|Да| D[ConcurrentSkipListMap]
  B -->|Нет| E[TreeMap]

Краткая глоссарий на одну строку

Map — коллекция пар “ключ→значение”; TreeMap — упорядоченная реализация Map на красно‑чёрном дереве.

Резюме

TreeMap полезен, когда требуется упорядоченный доступ по ключам и поддержка диапазонных операций. Он медленнее HashMap по среднему времени доступа, но даёт полезные возможности для поиска ближайших ключей и работы с поддиапазонами. Выбирайте реализацию Map, опираясь на требуемые свойства: порядок, поддержка null, потокобезопасность и требования по производительности.

Важно: при проектировании учитывайте реальные нагрузки и сценарии — иногда лучше комбинировать структуры или использовать специализированные реализации.