📦 Розділ 4 · Питання #16

Коли використовувати TreeMap

У переважній більшості повсякденних завдань стандартним вибором є HashMap, оскільки він забезпечує середню складність операцій $O(1)$. Проте існують специфічні сценарії, де вико...

📦 Колекції 📄 Вихідний Markdown

🟢 Junior Level

1. Призначення TreeMap

TreeMap — це реалізація інтерфейсу NavigableMap, заснована на збалансованому червоно-чорному дереві, яка зберігає всі записи строго відсортованими за ключами.

У переважній більшості повсякденних завдань стандартним вибором є HashMap, оскільки він забезпечує середню складність операцій $O(1)$. Проте існують специфічні сценарії, де використання HashMap неможливе або неефективне, і необхідний саме TreeMap.

                    ┌─────────────────────────┐
                    │      Потрібна Map?      │
                    └────────────┬────────────┘
                                 │
                 ┌───────────────┴───────────────┐
                 ▼                               ▼
       Потрібне сортування ключів       Сортування НЕ потрібне
       або діапазонний пошук?                    │
                 │                               ▼
                 ▼                            HashMap
              TreeMap                     (або LinkedHashMap)

2. Головні критерії вибору: коли використовувати TreeMap

  1. Необхідний діапазонний пошук (Range Queries): вибірка всіх записів в інтервалі від $A$ до $B$ (subMap(), headMap(), tailMap()).
  2. Необхідний пошук найближчого сусіда (Nearest Neighbor): пошук ключа, найбільшого з тих, що менші за заданий (floorKey()), або найменшого з тих, що більші за заданий (ceilingKey()).
  3. Неперервне сортування в реальному часі: коли нові ключі надходять потоком і структура повинна в будь-який момент віддавати мінімальний або максимальний ключ (firstEntry(), lastEntry(), pollFirstEntry()).

🟡 Middle Level

1. Практичні сценарії застосування

Сценарій А: Ступенева тарифікація та шкали оподаткування

Коли бізнес-правила прив’язані до числових інтервалів, TreeMap розв’язує задачу за $O(\log N)$ без громіздких конструкцій if-else:

NavigableMap<Integer, Double> taxBrackets = new TreeMap<>();
taxBrackets.put(0, 0.0);        // до 10 000 ставка 0%
taxBrackets.put(10_000, 0.10);  // від 10 000 до 50 000 ставка 10%
taxBrackets.put(50_000, 0.20);  // від 50 000 до 100 000 ставка 20%
taxBrackets.put(100_000, 0.35); // понад 100 000 ставка 35%

int annualIncome = 75_000;
// floorEntry знаходить найбільший поріг <= 75 000:
Map.Entry<Integer, Double> bracket = taxBrackets.floorEntry(annualIncome);

System.out.printf("Дохід: %d, Ставка: %.0f%%%n", annualIncome, bracket.getValue() * 100);
// Виведе: Дохід: 75000, Ставка: 20%

Сценарій Б: Часові ряди (Time Series) та ковзні вікна

Зберігання телеметрії, метрик чи біржових котирувань, прив’язаних до часових міток Instant або Long timestamp:

NavigableMap<Long, Double> stockPrices = new TreeMap<>();
stockPrices.put(1700000000L, 150.25);
stockPrices.put(1700000060L, 150.50);
stockPrices.put(1700000120L, 151.10);

long windowStart = 1700000000L;
long windowEnd = 1700000100L;

// Отримання зрізу даних за вказаний інтервал за O(1) пам'яті:
Map<Long, Double> window = stockPrices.subMap(windowStart, true, windowEnd, true);

Сценарій В: Префіксний пошук рядкових ключів

Завдяки лексикографічному сортуванню рядків у дереві можна миттєво вибирати ключі із заданим префіксом:

NavigableMap<String, User> userIndex = new TreeMap<>();
// Вибірка всіх користувачів, чий логін починається на "admin_":
Map<String, User> admins = userIndex.subMap("admin_", "admin_\uffff");

2. Коли TreeMap використовувати НЕ МОЖНА (Антипатерни)

  1. Звичайний словник (Key-Value Cache): Якщо потрібен просто швидкий доступ за ключем без вимоги впорядкованості, TreeMap працюватиме в 5–50 разів повільніше за HashMap і споживатиме значно більше пам’яті.
  2. Потрібен порядок додавання (Insertion-Order): Для збереження хронології вставки слід обирати LinkedHashMap, а не TreeMap.
  3. Рідкісне одноразове сортування: Якщо дані додаються тисячами, а відсортований перелік потрібен лише раз на добу для звіту, використання TreeMap є антипатерном. Набагато ефективніше накопичувати дані в HashMap ($O(1)$ на запис), а перед генерацією звіту одноразово відсортувати ключі: 
    // ЕФЕКТИВНІШЕ при рідкісному сортуванні:
List<Key> sortedKeys = new ArrayList<>(hashMap.keySet());
Collections.sort(sortedKeys); // O(N log N) один раз

🔴 Senior Level

1. Архітектурні компроміси: алгоритміка проти апаратного кешу

Характеристика HashMap TreeMap
Алгоритмічна складність пошуку $O(1)$ $O(\log N)$
Локальність посилань (Cache Locality) Добра (плаский масив бакетів) Низька (розкидані вузли в купі)
CPU Cache Misses при пошуку 1–2 промахи кешу L1/L2 $\approx \log_2 N$ промахів кешу (10–25 разів)
Витрати пам’яті на запис (64-bit) $\approx 32$ байти (Node) $\approx 40$ байтів (Entry з 5 посиланнями)
Вплив на Garbage Collector Помірний Високий (складний граф об’єктів)

У реальних бенчмарках на сучасних процесорах при $N = 1\,000\,000$ пошук у TreeMap програє HashMap не просто в $\log_2(10^6) \approx 20$ разів, а в 50–100 разів через постійні простої конвеєра CPU під час очікування завантаження рядків пам’яті з RAM при переходах за посиланнями left / right.

2. Concurrency: TreeMap проти ConcurrentSkipListMap

TreeMap принципово не є потокобезпечним. Якщо багатопотоковому застосунку потрібна відсортована карта, існують два підходи:

  1. Collections.synchronizedSortedMap(new TreeMap<>()) — грубе блокування (Coarse-Grained Locking). Блокує всю мапу на будь-яку операцію get або put. Призводить до жорстких простоїв потоків і деградації throughput.
  2. ConcurrentSkipListMap — промисловий стандарт. Побудований на базі ймовірнісної структури даних Skip List (список із пропусками). Забезпечує ту саму складність $O(\log N)$ та навігаційні методи (floorKey, subMap), проте операції виконуються Lock-Free (через атомарні CAS-інструкції процесора), чудово масштабуючись на будь-яку кількість процесорних ядер.

3. Механіка представлень (Live Views)

Методи subMap(), headMap(), tailMap() повертають не копії, а живі проєкції (AscendingSubMap / DescendingSubMap):

  • Створення представлення відбувається за $O(1)$ без виділення додаткової пам’яті під елементи.
  • Додавання елемента через представлення (subMap.put(k, v)) фізично вставляє запис у вихідне дерево.
  • Будь-яка спроба вставити ключ, що виходить за межі діапазону, негайно викидає IllegalArgumentException: key out of range.
  • При видаленні записів із subMap вони видаляються з основного TreeMap.

🎯 Шпаргалка для інтерв’ю

30-секундна відповідь (Elevator Pitch)

«TreeMap слід використовувати тоді й тільки тоді, коли ключовою вимогою системи є підтримання записів у відсортованому порядку, або необхідність виконання діапазонних запитів (subMap, headMap) та операцій пошуку найближчих ключів (floorKey, ceilingKey). В усіх інших випадках за замовчуванням слід обирати HashMap завдяки гарантованій швидкості $O(1)$ проти $O(\log N)$ і відсутності постійних промахів процесорного кешу. Якщо відсортована мапа потрібна в конкурентному багатопотоковому середовищі, замість TreeMap обирають ConcurrentSkipListMap».

3 каверзних питання на інтерв’ю з відповідями

1. Необхідно показувати користувачам перелік товарів, відсортований за ціною, один раз на добу в нічному звіті. Товари додаються безперервно протягом дня. Яку колекцію обрати для зберігання?

Відповідь: HashMap (або ConcurrentHashMap залежно від багатопотоковості). Зберігання в TreeMap сповільнить кожну денну вставку до $O(\log N)$ і створить зайве навантаження на GC та пам’ять. Значно вигідніше накопичувати дані за $O(1)$ у HashMap, а вночі один раз витягнути список значень і відсортувати його через Collections.sort() за $O(N \log N)$.

2. Чому як потокобезпечна альтернатива TreeMap у JDK реалізований ConcurrentSkipListMap на списках із пропусками, а не «ConcurrentTreeMap» на червоно-чорному дереві?

Відповідь: Балансування червоно-чорного дерева при вставці чи видаленні вимагає поворотів кількох пов’язаних вузлів (аж до кореня). Реалізувати дрібногранулярні блокування (Fine-Grained Locks) або CAS-операції на обертовому дереві математично надзвичайно важко без блокування великих піддерев. Список із пропусками (Skip List) складається з лінійних односпрямованих списків кількох рівнів, де додавання й видалення вузлів суворо локалізовані та елегантно реалізуються за допомогою атомарних CAS-інструкцій без блокувань.

3. Що станеться, якщо під час роботи з subMap модифікувати базовий TreeMap?

Відповідь: Оскільки subMap є «живим представленням» (Live View), будь-які валідні зміни в основному TreeMap у межах діапазону subMap негайно стануть видимими через subMap. Проте якщо під час ітерації по subMap у вихідну мапу буде додано новий запис у тому ж потоці, ітератор викине ConcurrentModificationException (fail-fast).

Типові помилки та Red Flags

  • ❌ Використання TreeMap заради збереження порядку вставки: Порядок додавання гарантує LinkedHashMap, тоді як TreeMap завжди сортує дані за компаратором.
  • ❌ Спроба покласти ключ null у TreeMap: Викине NullPointerException, оскільки дерево зобов’язане викликати метод compareTo().
  • ❌ Застосування Collections.synchronizedSortedMap(treeMap) у високонавантажених системах: Створює вузьке місце на глобальному моніторі; правильне рішення — ConcurrentSkipListMap.
  • ❌ Незбіг compareTo() та equals() у бізнес-ключах: Призведе до перезапису різних сутностей, якщо їхній compareTo() повернув 0.

Пов’язані теми