Що відбувається при досягненні 8 елементів в одному бакеті

При досягненні 8 елементів в одному кошику (TREEIFY_THRESHOLD = 8) HashMap ініціює процедуру оптимізації пошуку, викликаючи внутрішній метод treeifyBin(). Проте створення червон...

🟢 Junior Level

Короткий опис для співбесіди (30 секунд)

При досягненні 8 елементів в одному кошику (TREEIFY_THRESHOLD = 8) HashMap ініціює процедуру оптимізації пошуку, викликаючи внутрішній метод treeifyBin(). Проте створення червоно-чорного дерева відбувається не завжди:

Якщо загальна місткість таблиці менша ніж 64 (table.length < 64): дерево НЕ створюється. Замість цього викликається метод resize(), що подвоює місткість масиву кошиків. Архітектори JDK виходять із того, що при невеликій таблиці колізія викликана нестачею кошиків, і ресайз розподілить елементи по нових бакетах.
Якщо загальна місткість таблиці 64 або більше (table.length >= 64): зв’язний список кошика перетворюється на збалансоване червоно-чорне дерево (TreeNode), скорочуючи час пошуку з лінійного $O(n)$ до логарифмічного $O(\log n)$.

Порівняльна таблиця розгалуження поведінки при 8 елементах

Критерій	Місткість таблиці $< 64$ (`MIN_TREEIFY_CAPACITY`)	Місткість таблиці $\ge 64$
Реакція `treeifyBin()`	Виклик `resize()` (подвоєння місткості)	Перетворення списку на червоно-чорне дерево
Що відбувається з бакетом	Елементи розподіляються на 2 різні бакети	Елементи залишаються в тому самому бакеті у вигляді `TreeNode`
Складність пошуку	Повертається до $O(1)$ у нових кошиках	Знижується до $O(\log k)$ всередині поточного кошика
Витрати пам’яті	Виділяється новий масив посилань `table[]`	Вузли `Node` замінюються важчими `TreeNode` (~2x RAM)

Демонстрація поведінки в Java 21

import java.lang.reflect.Field;
import java.util.HashMap;

public class TreeifyThresholdDemo {

    // Клас із константним hashCode для примусової колізії
    record BadKey(int id) {
        @Override
        public int hashCode() {
            return 42; // Усі екземпляри потрапляють строго в один кошик!
        }
    }

    public static void main(String[] args) throws Exception {
        HashMap<BadKey, String> map = new HashMap<>();

        // Додаємо 8 елементів у мапу з початковою місткістю 16
        for (int i = 1; i <= 8; i++) {
            map.put(new BadKey(i), "Val-" + i);
        }

        // При додаванні 8-го елемента місткість таблиці була 16 (< 64).
        // Замість дерева відбувся resize() до 32!
        printTableCapacity(map); // Виведе capacity = 64 (після двох ресайзів: 16 -> 32 -> 64)
    }

    private static void printTableCapacity(HashMap<?, ?> map) throws Exception {
        Field tableField = HashMap.class.getDeclaredField("table");
        tableField.setAccessible(true);
        Object[] table = (Object[]) tableField.get(map);
        System.out.println("Поточна місткість таблиці (table.length): " + (table != null ? table.length : 0));
    }
}

🟡 Middle Level

Чому `resize()` кращий за деревофікацію

При проєктуванні HashMap інженери надали пріоритет розширенню масиву перед побудовою дерев із двох фундаментальних причин:

Справжнє усунення колізії: при подвоєнні місткості таблиці ($oldCap \to 2 \times oldCap$) кожен елемент із ймовірністю $50\%$ переходить у новий кошик (oldIndex + oldCap) залежно від біта (hash & oldCap). Це ліквідує колізію в корені, повертаючи пошук до миттєвого $O(1)$.
Економія оперативної пам’яті: вузол дерева TreeNode удвічі важчий за звичайний вузол Node (56–64 байти проти 32 байтів). Перетворення кошика на дерево лікує симптом (повільний пошук), але посилює накладні витрати за пам’яттю та сповільнює вставку.

Пороги 8 та 6: Теорія ймовірностей та Гістерезис

У коді HashMap зафіксовано три взаємопов’язані константи:

TREEIFY_THRESHOLD = 8 — поріг перетворення списку на дерево;
UNTREEIFY_THRESHOLD = 6 — поріг зворотного перетворення дерева на список;
MIN_TREEIFY_CAPACITY = 64 — мінімальна місткість для дозволу деревофікації.

1. Статистичне обґрунтування константи 8 (Пуассон):

При коефіцієнті завантаження $0.75$ розподіл ключів за кошиками описується розподілом Пуассона із середнім $\lambda = 0.5$. Ймовірність випадково отримати 8 елементів в одному кошику становить: $P(8) = \frac{e^{-0.5} \times 0.5^8}{8!} \approx 0.00000006 \quad (6 \times 10^{-8})$ Це математично виняткова подія. Якщо вона сталася, то або таблиця перевантажена, або застосунок перебуває під атакою Hash Flooding DoS.

2. Зазор у 2 одиниці (Гістерезис):

Якби поріг перетворення на дерево й назад був однаковим (наприклад, 8 та 7), то в застосунку, що регулярно додає та видаляє один елемент навколо цієї межі, відбувався б дребезг структури (Thrashing / Flapping): постійна дорога перебудова дерева на список і назад. Зазор у 2 одиниці забезпечує стабільність.

🔴 Senior Level

Внутрішня будова процедури `treeifyBin()`

Як HotSpot трансформує список у червоно-чорне дерево під капотом:

[ Head Node 1 ] ──next──► [ Node 2 ] ──next──► [ Node 3 ] ... (8 елементів)
                               │
                      treeifyBin() (таблиця >= 64)
                               │
                               ▼
        1. Заміна Node на TreeNode та зв'язування у двозв'язний список:
[ TreeNode 1 ] ◄──prev/next──► [ TreeNode 2 ] ◄──prev/next──► [ TreeNode 3 ] ...
                               │
                               ▼
        2. Виклик treeify() — побудова збалансованого дерева:
                          [ Root: TreeNode 4 ] (Black)
                                ╱            ╲
                     [ TreeNode 2 ]        [ TreeNode 6 ] (Red)
                      ╱          ╲          ╱          ╲

Перший прохід (Заміна типу нод): метод проходить однозв’язним списком, замінюючи кожен Node на TreeNode зі збереженням вихідних зв’язків next та додаванням посилань prev. Виходить плаский двозв’язний список вузлів TreeNode.
Другий прохід (TreeNode.treeify()): перший вузол оголошується коренем дерева (root). Усі наступні вузли вставляються в бінарне дерево з перевіркою балансування (balanceInsertion) — виконуються ліві та праві повороти (Rotations) і перефарбовування вузлів (Recoloring).
Метод moveRootToFront(): корінь червоно-чорного дерева може змінитися в результаті обертань. Цей метод гарантує, що вузол root також стане першим елементом у масиві table[index], щоб доступ до кореня дерева відбувався без проходу посиланнями prev.

Архітектура вирішення порядку: `Comparable` та `tieBreakOrder`

Для ефективної побудови бінарного дерева пошуку елементи зобов’язані мати відношення строгого порядку ($<$ або $>$).

// Перевірка на реалізованість інтерфейсу Comparable у HashMap HotSpot:
static Class<?> comparableClassFor(Object x) {
    if (x instanceof Comparable) {
        Class<?> c = x.getClass();
        if (c == String.class) // Швидкий шорткат для рядків
            return c;
        Type[] ts = c.getGenericInterfaces();
        // Глибокий рефлексивний аналіз: перевіряється, чи параметризований Comparable тим самим класом!
    }
    return null;
}

Що відбувається, якщо ключі НЕ реалізують `Comparable`:

Якщо ключі належать різним класам — вони впорядковуються за іменами класів: a.getClass().getName().compareTo(b.getClass().getName()).
Якщо імена класів однакові або compareTo() повернув 0 (при нерівності за equals()), викликається tieBreakOrder():
```
static int tieBreakOrder(Object a, Object b) {
    int d = (System.identityHashCode(a) <= System.identityHashCode(b) ? -1 : 1);
    return d;
}
```
Як арбітр виступає нативний геш адреси об’єкта з Mark Word.

Деревофікація в продакшені як індикатор архітектурного дефекту

У моніторингу промислових систем перехід кошиків у стан TreeNode повинен викликати алерт:

Дефект бізнес-ключа: розробник перевизначив hashCode() за неселективним полем (наприклад, статус замовлення OrderStatus, що має лише 5 варіацій);
Витік пам’яті в Young Gen: часті операції вставки в дерево призводять до постійних алокацій та балансувань, збільшуючи паузи Stop-The-World (GC STW).

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

1. 30-секундний есенс (Elevator Pitch)

При досягненні 8 елементів в одному кошику викликається treeifyBin(). Якщо розмір таблиці менший за 64 (MIN_TREEIFY_CAPACITY), дерево не створюється — замість цього викликається resize(), який розносить елементи по різних кошиках. Якщо місткість $\ge 64$, список перебудовується в червоно-чорне дерево (TreeNode), знижуючи найгіршу складність пошуку з $O(n)$ до $O(\log n)$. Зворотний перехід у список відбувається при зменшенні елементів до $\le 6$ (гістерезис для захисту від дребезгу).

2. 4 каверзних питання з глибокими відповідями

Питання 1: У якому випадку при накопиченні 8 елементів у кошику дерево НЕ буде створено, і що станеться замість цього?

Відповідь: Дерево не буде створено, якщо поточна довжина масиву кошиків table.length < 64. Замість деревофікації HashMap викличе метод resize(), який подвоїть місткість таблиці (наприклад, із 16 до 32 або з 32 до 64). При подвоєнні таблиці елементи з переповненого кошика перерозподіляються за двома різними бакетами на основі бітової перевірки (hash & oldCap) == 0. У більшості випадків це повністю усуває локальну колізію без оверхеду на побудову дерева.

Питання 2: Як `HashMap` перевіряє, чи реалізує ключ інтерфейс `Comparable`, і чому ця перевірка складніша за звичайний `instanceof`?

Відповідь: Простої перевірки key instanceof Comparable недостатньо, тому що інтерфейс Comparable<T> параметризований. Клас ключа повинен реалізовувати порівняння саме з об’єктами свого типу (Comparable<MyClass>), а не довільного супертипу. Метод comparableClassFor() через reflection обходить generic-інтерфейси класу (c.getGenericInterfaces()) і верифікує фактичний аргумент типу. Для рядків зроблено мікрооптимізацію: if (c == String.class) return c;.

Питання 3: Навіщо викликається метод `moveRootToFront()` після балансування дерева?

Відповідь: У HashMap комірка масиву table[index] зберігає пряме посилання на перший вузол кошика. У результаті балансування червоно-чорного дерева (повороти навколо ребер) корінь дерева (root) може змінитися. Метод moveRootToFront() переставляє вузол-корінь на самий початок двозв’язного списку TreeNode та оновлює вказівник у комірці table[index] = root. Це гарантує, що будь-який наступний пошук або вставка почнеться з кореня за $O(1)$ без попереднього обходу посилань prev.

Питання 4: Чому поява дерев `TreeNode` у продакшен-моніторингу вважається симптомом проблеми?

Відповідь: При чесній реалізації hashCode() ймовірність скупчення 8 елементів в одному кошику становить $6 \times 10^{-8}$ (розподіл Пуассона). Поява дерев свідчить або про грубу помилку в hashCode() (наприклад, повернення константи або гешування лише одного неунікального поля), або про зовнішню DoS-атаку на генерацію колізій (Hash Flooding). Дерево рятує систему від падіння, але погіршує час вставки й витрачає вдвічі більше пам’яті.

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

❌ «При 8 елементах кошик завжди стає деревом.»
Правильно: Дерево створюється тільки за умови table.length >= 64. Інакше викликається resize().

❌ «Дерево перетворюється назад на список, щойно елементів стало менше 8.»
Правильно: Поріг де-деревофікації дорівнює 6 (UNTREEIFY_THRESHOLD). Зазор у 2 елементи запобігає дребезгу структури.

❌ «Дерево усуває колізію.»
Правильно: Дерево не усуває колізію, а лише прискорює пошук з $O(n)$ до $O(\log n)$ усередині переповненого бакета. Колізію усуває тільки resize().