🟢 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]]