🟢 Junior Level

Коли два ключі потрапляють в одну корзину, HashMap не губиться — вона зберігає їх обидва у вигляді ланцюжка (linked list).

Як це працює: Кожен елемент в бакеті містить посилання next на наступний. Бакет вказує на перший елемент, перший — на другий, і так далі. Як вагони поїзда: щоб знайти потрібний, потрібно пройти всі від початку.

Проста аналогія: Уявіть поштову скриньку, в яку поклали два листи для різних людей. Всередині скриньки лежить список: “Лист 1 — для Аліси, Лист 2 — для Боба”. Коли приходить листоноша, він перевіряє обидва листи.

Приклад:

HashMap<String, String> map = new HashMap<>();
map.put("Aa", "Hello");    // hashCode = 2112
map.put("BB", "World");    // hashCode = 2112 — колізія!
// Обидва елементи зберігаються в одній корзині
System.out.println(map.get("Aa")); // "Hello" — знаходить правильний
System.out.println(map.get("BB")); // "World" — теж знаходить

🟡 Middle Level

Java 7 vs Java 8+

Характеристика	Java 7	Java 8+
Місце вставки	На початок списку	В кінець списку
Структура	Тільки зв’язний список	Список → Червоно-чорне дерево
Складність	O(n)	O(log n)
Зациклення	Можливе при багатопотоковому resize	Виправлено

Чому поріг = 8? Для k ≤ 7 зв’язний список швидший за дерево: накладні витрати на обхід дерева (посилання parent/left/right, перевірки кольору) переважують вигоду від O(log k). Саме тому treeification починається з 8, а не з 2 або 3.

Механізм Treeification

Параметри переходу до дерева:

• TREEIFY_THRESHOLD = 8 — при 9-му елементі викликається treeifyBin()
• MIN_TREEIFY_CAPACITY = 64 — якщо таблиця менше 64, робиться resize замість treeification
• UNTREEIFY_THRESHOLD = 6 — зворотний перехід при зменшенні

Алгоритм put при колізії

1. Обчислюється індекс бакета
2. Ітерується існуюча структура (список або дерево)
3. Швидка перевірка: p.hash == hash
4. Точна перевірка: p.key == key || p.key.equals(key)
5. Якщо збіг — оновлюється значення
6. Якщо ні — нова нода додається в хвіст
7. При довжині списку >= 8 — treeification (Java 8+)

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

1. Поганий hashCode() — викликає масові колізії і деградацію
2. Використання HashMap в багатопотоковості — колізії поглибують гонки даних
3. Мутабельні ключі — зміна ключа робить елемент недоступним

🔴 Senior Level

Internal Implementation

При колізії HashMap проходить по ланцюжку:

for (int binCount = 0; ; ++binCount) {
    if ((e = p.next) == null) {
        p.next = newNode(hash, key, value, null);
        if (binCount >= TREEIFY_THRESHOLD - 1)
            treeifyBin(tab, hash);
        break;
    }
    if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
        break;
    p = e;
}

Оптимізація: спочатку порівнюється hash (швидке int-порівняння), і тільки потім викликається equals().

TreeNode Structure

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent, left, right, prev;
    boolean red;
    // + успадковує hash, key, value, next
}

TreeNode займає ~64-80 байт vs ~32-48 байт у Node. Тому treeification — це компроміс між швидкістю і пам’яттю.

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

Список vs Дерево:

• Список: мінімум пам’яті, але O(k) пошук
• Дерево: O(log k) пошук, але ~2x пам’ять і overhead на балансування
• Поріг 8 обрано статистично: при хорошому hashCode ймовірність 8 колізій мізерна

Багатопотоковий resize

У Java 7 вставка в голову списку при зміні порядку елементів на зворотний. У багатопотоковому середовищі це створювало циклічні посилання (infinite loop при get()). Java 8 перейшла на вставку в хвіст, зберігши порядок. У ConcurrentHashMap використовується CAS + synchronized на голові бакета.

CAS (Compare-And-Swap) — атомарна операція процесора: «порівняй значення з очікуваним і, якщо збігається, заміни на нове». Використовується для потокобезпеки без блокувань.

GC Impact

Сильні колізії створюють навантаження на GC:

• Багато дрібних об’єктів Node
• TreeNode ще важче
• При частих put/remove — churn в Young Gen

Best Practices

1. Якісний hashCode() — найкращий захист від колізій
2. Для ключів-об’єктів реалізуйте Comparable — це прискорює treeification
3. У production моніторинг: зростання latency get/put = ознака колізій

---

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

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

• Separate Chaining (метод ланцюжків) — використовується в HashMap: колізії = список/дерево в бакеті
• Java 7: вставка в голову списку, Java 8+: вставка в хвіст (запобігає зацикленню)
• Дерево при 8 елементах, зворотний перехід при 6 (гістерезис для стабільності)
• Алгоритм put при колізії: спочатку перевірка hash (швидко), потім equals (точно)
• TreeNode займає ~2x більше пам’яті ніж Node (~64-80 байт vs ~32-48 байт)
• CAS + synchronized на голові бакета — як ConcurrentHashMap вирішує багатопотокові колізії

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

• Чому поріг = 8? — для k ≤ 7 список швидший за дерево (менше overhead на посилання і балансування)
• Чому зворотний перехід при 6, а не 7? — гістерезис: запобігає дребезгу при коливаннях
• Що буде якщо всі hashCode = 1? — Java 7: O(n²) DoS, Java 8+: дерево, але overhead
• Чому вставка в хвіст у Java 8? — вставка в голову перевертала список при resize → infinite loop в багатопотоковості

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

• «Колізії неможливі при хорошому hashCode» — можливі, просто рідкісні
• «Дерево завжди краще за список» — ні, для малих k список швидший
• «HashMap безпечна в багатопотоковості» — ні, навіть з treeification

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

• [[4. Що таке колізія в HashMap]]
• [[6. Що відбувається при досягненні 8 елементів в одному bucket]]
• [[7. Що таке контракт equals() і hashCode()]]
• [[22. Як працює HashMap в багатопотоковому середовищі]]