Коли використовувати 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]]