Какие знаешь особенности TreeMap?

TreeMap: Ключевые особенности

TreeMap — это реализация интерфейса SortedMap, основанная на красно-чёрном дереве (Red-Black Tree). Это одна из самых важных коллекций для работы с отсортированными данными в Java.

Основные характеристики

Порядок элементов: TreeMap хранит элементы в отсортированном порядке согласно естественному порядку ключей или компаратору, переданному в конструктор. Это означает, что при итерации ключи будут выдаваться в порядке возрастания.

Сложность операций: Все операции (put, get, remove, containsKey) выполняются за O(log n) времени благодаря структуре красно-чёрного дерева. Это медленнее, чем HashMap (O(1) в среднем), но гарантирует предсказуемую производительность.

Потокобезопасность: TreeMap не является потокобезопасным. Если требуется синхронизированный доступ, следует использовать:

SortedMap<String, Integer> syncMap = 
    Collections.synchronizedSortedMap(new TreeMap<>());

Null-значения: TreeMap не допускает null в качестве ключа, так как это нарушило бы логику сравнения. Однако null-значения в качестве значений разрешены.

Конструкторы и компараторы

Твём способами создать TreeMap:

// 1. С естественным порядком (ключи должны быть Comparable)
TreeMap<String, Integer> map1 = new TreeMap<>();

// 2. С пользовательским компаратором
TreeMap<String, Integer> map2 = new TreeMap<>((a, b) -> b.compareTo(a)); // обратный порядок

// 3. На основе существующего SortedMap
SortedMap<String, Integer> source = new TreeMap<>();
TreeMap<String, Integer> map3 = new TreeMap<>(source);

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

headMap(K toKey) — возвращает подмножество с ключами строго меньше toKey:

TreeMap<Integer, String> map = new TreeMap<>();
map.put(1, "one");
map.put(5, "five");
map.put(10, "ten");
SortedMap<Integer, String> head = map.headMap(5); // {1=one}

tailMap(K fromKey) — возвращает подмножество с ключами больше или равно fromKey:

SortedMap<Integer, String> tail = map.tailMap(5); // {5=five, 10=ten}

subMap(K fromKey, K toKey) — возвращает подмножество от fromKey включительно до toKey исключительно:

SortedMap<Integer, String> sub = map.subMap(1, 10); // {1=one, 5=five}

firstKey() / lastKey() — получить первый и последний ключ:

Integer first = map.firstKey(); // 1
Integer last = map.lastKey();   // 10

Применение в реальных задачах

TreeMap идеален для:

• Кэширование с вытеснением — хранение элементов в отсортированном виде
• Таблицы лидеров — быстрое получение топ-N элементов
• Диапазонные запросы — поиск всех элементов в диапазоне
• Автодополнение — хранение слов в отсортированном порядке

Важные отличия от HashMap

Заключение

TreeMap — это мощный инструмент для работы с отсортированными данными. Используй его, когда требуется гарантированный порядок элементов или быстрые диапазонные запросы, но помни о немного более высокой стоимости операций по сравнению с HashMap.