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

🟢 Junior Level

TreeMap — отсортированная Map, где ключи всегда в порядке.

Используйте TreeMap когда:

Нужна сортировка по ключам
Нужен поиск по диапазону
Нужен “ближайший” ключ

TreeMap<Integer, String> map = new TreeMap<>();
map.put(10, "A");
map.put(50, "B");
map.put(30, "C");

// Сортировка: {10=A, 30=C, 50=B}

// Ближайший ключ
map.floorKey(25);   // → 10 (ближайший ≤ 25)
map.ceilingKey(25); // → 30 (ближайший ≥ 25)

🟡 Middle Level

Когда TreeMap нужен

1. Диапазонный поиск:

TreeMap<Integer, String> taxBrackets = new TreeMap<>();
taxBrackets.put(0, "0%");
taxBrackets.put(10000, "10%");
taxBrackets.put(50000, "20%");

// Налоговая ставка для дохода 35,000
String rate = taxBrackets.floorEntry(35000).getValue();
// → "10%"

// HashMap НЕ сможет!

2. Сортированные отчёты:

TreeMap<LocalDate, Report> reports = new TreeMap<>();
// Всегда в хронологическом порядке
// subMap для диапазона дат

3. Префиксный поиск:

TreeMap<String, Data> index = new TreeMap<>();
// Все ключи с префиксом "user:"
SortedMap<String, Data> users = index.subMap("user:", "user{");

Когда TreeMap НЕ нужен

// ❌ Просто нужен словарь
Map<String, Integer> map = new TreeMap<>();  // O(log n) — дерево, нужно поддерживать порядок
// ✅ HashMap
Map<String, Integer> map = new HashMap<>();  // O(1) — хеш-таблица, быстрая вставка/поиск

// ❌ Нужен порядок вставки
Map<String, Integer> map = new TreeMap<>();  // Сортирует!
// ✅ LinkedHashMap
Map<String, Integer> map = new LinkedHashMap<>();  // Порядок вставки

🔴 Senior Level

Производительность

TreeMap: O(log n) на каждую операцию
HashMap: O(1)

→ 1 млн элементов:
  HashMap: ~0.001 мс
  TreeMap: ~0.05 мс (в 50 раз медленнее!)

Ориентировочно для 1 млн Integer-ключей на современном CPU. Реальные цифры зависят от JVM и типа ключей. Главное — порядок разницы: O(1) vs O(log n).

→ Не используйте TreeMap как основное хранилище
  если сортировка нужна редко!

Альтернатива: сортировка “на лету”

// ❌ TreeMap для редкой сортированной итерации
TreeMap<K, V> sortedMap = new TreeMap<>();
// O(log n) на каждую вставку

// ✅ HashMap + сортировка при итерации
HashMap<K, V> map = new HashMap<>();
List<K> sortedKeys = new ArrayList<>(map.keySet());
Collections.sort(sortedKeys);
// O(n log n) один раз при итерации
// O(1) на вставку!

View: subMap, headMap, tailMap

NavigableMap<Integer, String> view = map.subMap(10, true, 50, true);
// → "Живое" представление, не копия!
// → O(1) создание

view.put(30, "X");  // Добавляет в ИСХОДНУЮ map
map.remove(30);     // Удаляет из view тоже!

view.put(100, "Y"); // → IllegalArgumentException!
// → 100 вне диапазона [10, 50]

ConcurrentSkipListMap

// TreeMap НЕ thread-safe!
// Для многопоточной сортированной мапы:
ConcurrentSkipListMap<K, V> map = new ConcurrentSkipListMap<>();
// → Skip List вместо дерева
// → O(log n), lock-free

// Skip List = probabilistic структура с «экспресс-полосами» для ускорения поиска.
// Проще в реализации и lock-free, но использует больше памяти, чем дерево.

Null ключи

// TreeMap не принимает null!
map.put(null, "value");  // → NullPointerException!

// Обходной путь (не рекомендуется):
TreeMap<String, String> map = new TreeMap<>(
    Comparator.nullsFirst(Comparator.naturalOrder())
);
map.put(null, "value");  // OK, null первый

Production Experience

Реальный сценарий: Time-series данные

// Датчики: timestamp → measurement
TreeMap<Long, SensorData> data = new TreeMap<>();

// Данные за последний час
Map<Long, SensorData> lastHour = data.tailMap(
    System.currentTimeMillis() - 3600000
);

// Ближайшее измерение к времени
Map.Entry<Long, SensorData> closest = data.floorEntry(targetTime);

Best Practices

TreeMap только для сортировки/диапазонов
HashMap — по умолчанию
Сортировка “на лету” если редко нужна
View = live, не копия
ConcurrentSkipListMap для многопоточности
null запрещён без custom Comparator
Память в 3-4 раза больше HashMap

Резюме для Senior

TreeMap = сортировка + навигация + диапазоны
O(log n) vs O(1) у HashMap
floorKey/ceilingKey = ближайший ключ
subMap = live представление диапазона
Не используйте если сортировка редко нужна
ConcurrentSkipListMap для concurrency
null запрещён (без Comparator)
Память > HashMap

🎯 Шпаргалка для интервью

Обязательно знать:

TreeMap = O(log n), сортировка ключей + навигация (floorKey, ceilingKey, subMap) — НЕ для обычных словарей
HashMap = O(1) — по умолчанию, TreeMap в ~50 раз медленнее при 1 млн элементов
Диапазонный поиск: subMap для временных рядов, налоговых ставок, префиксного поиска
View (subMap, headMap, tailMap) = live представление, не копия — O(1) создание
TreeMap НЕ thread-safe — для многопоточности ConcurrentSkipListMap (skip list, lock-free, O(log n))
Null-ключи запрещены (без custom Comparator nullsFirst/nullsLast)
Память: в 3-4 раза больше HashMap из-за узлов дерева (left, right, parent, color)
Альтернатива редкой сортировки: HashMap + Collections.sort(keySet) — O(1) вставка, O(n log n) сортировка по запросу

Частые уточняющие вопросы:

Когда TreeMap — единственный выбор? — Когда нужен диапазонный поиск (subMap) или «ближайший» ключ (floorKey/ceilingKey). HashMap этого не умеет.
Что такое live view и почему это важно? — subMap возвращает не копию, а представление. Добавление/удаление через view влияет на исходную мапу. Нельзя добавить элемент вне диапазона.
Чем ConcurrentSkipListMap отличается от TreeMap? — Thread-safe, использует skip list вместо дерева, lock-free операции, но больше памяти.
Почему не использовать TreeMap как основное хранилище? — O(log n) на каждую операцию. Если сортировка нужна редко — HashMap + сортировка при итерации дешевле.

Красные флаги (НЕ говорить):

❌ «TreeMap быстрее HashMap» — в 50 раз медленнее! Используйте только когда нужна сортировка
❌ «TreeMap thread-safe» — нет, ConcurrentSkipListMap для многопоточности
❌ «subMap копирует данные» — это live view, изменения отражаются в исходной мапе
❌ «TreeMap для порядка вставки» — для этого LinkedHashMap, TreeMap сортирует по ключам

Связанные темы:

[[15. В чём разница между HashMap, LinkedHashMap и TreeMap]]
[[13. Что такое TreeSet и как он работает]]
[[14. Что такое Map и какие реализации существуют]]
[[18. Что такое ConcurrentHashMap]]