🟢 Junior Level

Коли в одну корзину (бакет) потрапляє 8 елементів, HashMap вирішує оптимізувати пошук. Але перехід до дерева відбувається не завжди!

(Поведінка описана для Java 8+. У Java 7 treeification був відсутній.)

Що відбувається:

1. HashMap перевіряє загальний розмір таблиці
2. Якщо таблиця менше 64 бакетів — вона збільшує таблицю (resize)
3. Якщо таблиця 64 або більше — список перетворюється на дерево

Чому так: Resize переважніший за treeification: при подвоєнні таблиці елементи з однаковим hashCode розподіляться по ДВОМ різним бакетам (перевіряється один біт), що може повністю усунути колізію. Дерево ж лише оптимізує пошук всередині одного бакета, але не розв’язує колізію.

Приклад:

// Повний сценарій:
// capacity=16, threshold=12 → 8 елементів < 12 → resize НЕ відбувається
// При 13 елементі → resize до 32 → все ще < 64 → treeification НЕ спрацьовує
// При 25 елементі → resize до 64 → тепер >= 64 → treeification СПРАЦЬОВУЄ

🟡 Middle Level

Метод treeifyBin() і умова 64

if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
    resize();  // Збільшуємо таблицю
else {
    // Реальний перехід до дерева
}

Параметри:

• TREEIFY_THRESHOLD = 8 — тригер виклику treeifyBin()
• MIN_TREEIFY_CAPACITY = 64 — мінімальний розмір таблиці для дерева
• UNTREEIFY_THRESHOLD = 6 — зворотний перехід

Чому саме 8?

Ймовірність бакета з 8 елементами при loadFactor 0.75 і хорошому hashCode: 0.00000006 (розподіл Пуассона). Поява 8 елементів — це аномалія.

Чому розрив між 8 і 6? (Гістерезис)

Якби пороги були 8 і 7, при постійному додаванні/видаленні 8-го елемента HashMap нескінченно перебудовувала б структуру. Зазор у 2 одиниці забезпечує стабільність.

Вплив на продуктивність

Метрика	Список	Дерево
Пошук (8 елементів)	8 порівнянь	3 порівняння
Пошук (1024 елем.)	1024	10
Вставка	Швидка	Повільніша (балансування)
Пам’ять	~32 байт/Node	~64 байт/TreeNode

Типові помилки

1. Думати, що 8 елементів = завжди дерево — потрібно ще capacity >= 64
2. Ігнорувати сигнал — 8 колізій означають поганий hashCode()

Treeification — це сигнал проблеми

Якщо у production ви побачили treeification — це не «HashMap працює як задумано», а індикатор проблеми. Або у ключів зламаний hashCode(), або йде Hash Flooding Attack (зловмисник навмисне створює колізії).

🔴 Senior Level

Процес конвертації

1. Всі Node замінюються на TreeNode
2. Список перетворюється на двозв’язний (додається prev)
3. Будується червоно-чорне дерево з балансуванням

Червоно-чорне дерево — бінарне дерево, де кожна вершина ‘пофарбована’ в червоний або чорний колір. Правила розфарбування гарантують баланс: висота лівої і правої гілки відрізняється не більш ніж у 2 рази.

TieBreakOrder — механізм ‘розв’язання нічиєї’: коли два ключі мають однаковий hash і не реалізують Comparable, Java порівнює через System.identityHashCode() або імена класів.

При пошуку в дереві:

// 1. Порівняння за hash
// 2. Якщо хеши рівні і key implements Comparable — використовуємо compareTo()
// 3. Якщо ні — tieBreakOrder() через System.identityHashCode()

TieBreakOrder

Коли ключі не реалізують Comparable:

static int tieBreakOrder(Object a, Object b) {
    int d;
    if (a == null || b == null ||
        (d = a.getClass().getName().compareTo(b.getClass().getName())) == 0)
        d = (System.identityHashCode(a) <= System.identityHashCode(b) ? -1 : 1);
    return d;
}

Це fallback-механізм для побудови детермінованого дерева.

Архітектурні Trade-offs

Чому не створювати дерево одразу?

• TreeNode важче Node у 2 рази
• Для 2-7 елементів список швидший (менше overhead)
• Treeification — це захист від аномалій, а не стандартний режим

Edge Cases

1. Багатопотоковий resize — два потоки можуть одночасно тригерити treeification; ConcurrentHashMap вирішує це через CAS + synchronized на голові бакета
2. null-ключ — завжди в table[0], при 8 null-ключів (неможливо, бо null тільки один) — теоретично дерево для null не створюється

Performance

• Treeification: O(k * log k) для k елементів
• При 1024 колізіях: пошук 10 операцій vs 1024 (список) — виграш 100x
• Але вставка сповільнюється на ~30-50% через балансування

Production Monitoring

Аномальна treeification = індикатор проблем:

• Перевірте hashCode() ваших ключів
• Можливий Hash Flooding Attack
• У JFR дивіться HashMap.CollisionRate

---

🎯 Шпаргалка для співбесіди

Обов’язково знати:

• TREEIFY_THRESHOLD = 8, MIN_TREEIFY_CAPACITY = 64, UNTREEIFY_THRESHOLD = 6
• При 8 елементах І capacity < 64 — resize, НЕ дерево
• При 8 елементах І capacity >= 64 — treeification (список → червоно-чорне дерево)
• Гістерезис (8 → дерево, 6 → список) запобігає дребезгу структури
• TieBreakOrder: якщо ключі не Comparable — використовується System.identityHashCode()
• Реалізація Comparable для ключів прискорює treeification
• Treeification в production = сигнал проблеми (поганий hashCode або атака)

Часті уточнюючі питання:

• Чому resize переважніший за дерево? — resize рознесе елементи по різних бакетах, дерево лише оптимізує пошук в одному
• Що таке TieBreakOrder? — fallback при побудові дерева коли ключі не Comparable
• Чи може null-ключ створити дерево? — ні, null тільки один, колізій із самим собою немає
• Яка складність treeification? — O(k * log k) для k елементів

Червоні прапорці (НЕ говорити):

• «8 елементів = завжди дерево» — потрібно ще capacity >= 64
• «Treeification — штатний режим роботи» — це захист від аномалій
• «Дерево вирішує проблему колізій» — ні, лише оптимізує пошук всередині бакета

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

• [[2. Що таке bucket (корзина) в HashMap]]
• [[5. Як HashMap обробляє колізії]]
• [[17. Що таке capacity в HashMap]]
• [[18. Коли відбувається rehashing в HashMap]]