Як HashMap обробляє колізії

Для вирішення колізій HashMap використовує класичний алгоритм Separate Chaining (метод ланцюжків), посилений у Java 8 гібридною деревоподібною структурою.

🟢 Junior Level

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

Для вирішення колізій HashMap використовує класичний алгоритм Separate Chaining (метод ланцюжків), посилений у Java 8 гібридною деревоподібною структурою.

Коли два ключі з різними значеннями потрапляють в один кошик:

Зв’язний список (Java 8+ Tail Insertion): новий елемент поміщається в кінець (хвіст) однозв’язного списку колізій, прив’язуючись через поле Node.next.
Червоно-чорне дерево (Treeification): якщо кількість елементів в одному кошику досягає 8, а загальна місткість таблиці становить не менше ніж 64, зв’язний список автоматично перетворюється на збалансоване червоно-чорне дерево (TreeNode).
Пошук: при виклику get() мапа знаходить кошик, а потім проходить списком або деревом, спочатку перевіряючи збережений геш (p.hash == hash), а потім точний збіг ключів (k == key || key.equals(k)).

Порівняльна таблиця: Обробка колізій у Java 7 та Java 8+

Характеристика	Java 7	Java 8+
Спосіб вставки у список	На початок (Head Insertion)	У кінець (Tail Insertion)
Структура при глибоких колізіях	Однозв’язний список	Червоно-чорне дерево (`TreeNode`)
Складність найгіршого випадку	$O(n)$	$O(\log n)$
Багатопотоковий `resize()`	Викликав зациклення списку (100% CPU)	Зациклення усунуто (проте втрата даних можлива)
Умови деревофікації	Були відсутні	$\ge 8$ елементів у бакеті та місткість таблиці $\ge 64$

Демонстрація вирішення колізій у Java 21

import java.util.HashMap;

public class CollisionResolutionDemo {
    public static void main(String[] args) {
        HashMap<KeyWithCollision, String> map = new HashMap<>();

        KeyWithCollision k1 = new KeyWithCollision("id1", 42);
        KeyWithCollision k2 = new KeyWithCollision("id2", 42); // Однаковий hashCode!
        KeyWithCollision k3 = new KeyWithCollision("id3", 42); // Однаковий hashCode!

        // Усі три елементи потрапляють в один і той самий кошик:
        map.put(k1, "Value-1"); // Голова списку
        map.put(k2, "Value-2"); // Прив'язується до хвоста k1
        map.put(k3, "Value-3"); // Прив'язується до хвоста k2

        // Пошук за ключем успішно знаходить правильне значення через equals():
        System.out.println("k2 -> " + map.get(k2)); // Value-2
        System.out.println("Розмір мапи: " + map.size()); // 3
    }

    record KeyWithCollision(String id, int fixedHash) {
        @Override
        public int hashCode() {
            return fixedHash; // Штучна колізія
        }
    }
}

🟡 Middle Level

Покроковий алгоритм `putVal` при виникненні колізії

Коли обчислений індекс кошика вже зайнятий іншим вузлом, виконується наступний цикл:

// Фрагмент реалізації методу putVal() у HotSpot:
for (int binCount = 0; ; ++binCount) {
    if ((e = p.next) == null) {
        // Досягнуто хвоста списку — вставляємо новий вузол
        p.next = newNode(hash, key, value, null);
        // Якщо довжина ланцюжка досягла 8 (binCount >= 7)
        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;
}

Подвійна умова деревофікації (Treeify Conditions)

Багато розробників вважають, що поява 8 елементів у кошику завжди призводить до створення дерева. Це хибна думка:

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    // Якщо загальна місткість таблиці МЕНША за 64 — ДЕРЕВО НЕ СТВОРЮЄТЬСЯ!
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize(); // Замість дерева подвоюється таблиця!
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        // Перетворення списку на TreeNode
    }
}

TREEIFY_THRESHOLD = 8: довжина ланцюжка в кошику повинна бути не меншою за 8;
MIN_TREEIFY_CAPACITY = 64: розмір масиву кошиків повинен бути не меншим за 64.
Якщо місткість менша за 64 (наприклад, стандартні 16 або 32), HashMap вважає, що колізія викликана банальною тіснотою таблиці, і просто викликає resize(), розкидаючи елементи по нових кошиках.

Зворотне перетворення дерева на список (Untreeification) та гістерезис

Дерево — тимчасовий захисний захід. Якщо елементи видаляються (remove) або розділяються в процесі ресайзу (resize), дерево може перетворитися назад на список:

Поріг перетворення на дерево: $\ge 8$ елементів;
Поріг зворотного перетворення на список: $\le 6$ елементів (UNTREEIFY_THRESHOLD).

Навіщо потрібен зазор між 6 та 8 (Гістерезис):

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

🔴 Senior Level

Двоїста природа `TreeNode`: Дерево і Список одночасно

У вихідному коді OpenJDK клас TreeNode має незвичайну ієрархію:

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // Вузол-батько в червоно-чорному дереві
    TreeNode<K,V> left;    // Лівий нащадок
    TreeNode<K,V> right;   // Правий нащадок
    TreeNode<K,V> prev;    // Попередній вузол у двозв'язному списку
    boolean red;           // Колір вузла (True = Red, False = Black)
    // Від HashMap.Node успадковані: final int hash, final K key, V value, Node next
}

TreeNode зберігає дві структури даних одночасно:

За посиланнями left, right, parent вузли організовані у збалансоване червоно-чорне дерево для швидкого пошуку за $O(\log n)$;
За посиланнями next, prev вузли одночасно зв’язані у двозв’язний список!

Навіщо потрібна ця двоїстість:

Коли при ресайзі кошик потрібно розщепити на два нові (перевірка (e.hash & oldCap) == 0), JVM не обходить важке дерево! Вона миттєво ітерується пласким списком через e.next, ділить його на дві пачки і, якщо в кожній залишилося $\le 6$ елементів, миттєво розгортає їх у звичайні Node методом untreeify().

Механіка багу нескінченного циклу в Java 7 (Infinite Loop on Concurrent Resize)

Чому в Java 7 категорично заборонялося використовувати HashMap у багатопотоковому середовищі?

Причина: Head Insertion (вставка на початок списку):

У Java 7 метод transfer() при ресайзі брав елементи зі старої таблиці та вставляв їх у голову нової таблиці, змінюючи порядок елементів на протилежний.

Початковий стан кошика: [ A ] ──► [ B ] ──► null

Потік 1 починає ресайз: читає вузол e = A, запам’ятовує next = B. У цей момент ОС перемикає контекст (Thread 1 засинає);
Потік 2 встигає виконати повний ресайз:
- Вставляє A у нову таблицю;
- Вставляє B перед A (у голову!). Порядок інвертувався:
```
Нова таблиця: [ B ] ──► [ A ] ──► null
```
Потік 1 прокидається. Для нього e = A, next = B. Він вставляє A, а потім обробляє B.
У процесі маніпуляції вказівниками посилання A.next примусово спрямовується на B, у той час як у B.next вже стоїть вказівник на A.
Утворюється кільце: A ──► B ──► A ──► B ...
Будь-який наступний виклик map.get() або map.put() у цей кошик іде в нескінченний цикл while(e != null), споживаючи 100% одного ядра процесора.

У Java 8 перехід на Tail Insertion (вставку в хвіст) та розділення на дві черги (loHead/hiHead) гарантує збереження вихідного порядку елементів, повністю усуваючи ризик кільцевих посилань (хоча стан гонки та втрата оновлень у багатопотоковому HashMap як і раніше відбуваються).

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

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

Колізії в HashMap обробляються методом ланцюжків (Separate Chaining). У Java 8+ нові елементи додаються в хвіст списку (Tail Insertion), що виключило баг зациклення Java 7. При досягненні 8 елементів у ланцюжку та розмірі таблиці $\ge 64$ список трансформується в червоно-чорне дерево (TreeNode), знижуючи складність пошуку з $O(n)$ до $O(\log n)$. Якщо розмір таблиці $< 64$, замість дерева викликається resize(). При зменшенні вузлів до $\le 6$ дерево перетворюється назад на зв’язний список (гістерезис).

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

Питання 1: Чому `TreeNode` одночасно зберігає посилання і для дерева (`left`, `right`, `parent`), і для списку (`next`, `prev`)?

Відповідь: Це архітектурна оптимізація для здешевлення операцій ресайзу та зворотної де-деревофікації. Завдяки збереженню зв’язків списку (next/prev) при подвоєнні таблиці JVM не потрібно виконувати складний обхід вузлів дерева (in-order tree traversal). Мапа ітерується за вузлами як за звичайним списком за $O(k)$, розподіляючи елементи на два нові кошики за бітом (hash & oldCap). Якщо в новому кошику залишилося 6 або менше елементів, дерево тривіально перетворюється назад на Node без перебудови дерева.

Питання 2: Як саме відбувалося зациклення списку в Java 7 при багатопотоковому ресайзі, і чому хвостова вставка в Java 8 це виправила?

Відповідь: У Java 7 елементи при ресайзі переносилися в новий кошик через вставку в голову (Head Insertion), що розгортало порядок елементів на протилежний ($A \to B$ ставало $B \to A$). При конкурентному виконанні двом потокам вдавалося заплутати посилання так, що вказівник $A.next$ замикався на $B$, а $B.next$ — на $A$, утворюючи кільце. При наступному зверненні get() потік входив у нескінченний цикл зі 100% утилізацією CPU. У Java 8 елементи додаються строго в хвіст (Tail Insertion), зберігаючи незмінний відносний порядок слідування вузлів, що робить утворення циклів топологічно неможливим.

Питання 3: За яких точних умов червоно-чорне дерево перетворюється назад на зв’язний список?

Відповідь: Перетворення дерева на список (Untreeification) відбувається у двох сценаріях:

При ресайзі (resize()): якщо в процесі розділення кошика на lo та hi частини в одному з нових кошиків залишається $\le 6$ елементів (UNTREEIFY_THRESHOLD);
При видаленні елемента (remove()): перед видаленням перевіряється структура дерева. Якщо корінь (root), його нащадки (root.left, root.right) або онук root.left.left відсутні (дерево стало критично маленьким, зазвичай від 2 до 6 вузлів залежно від балансування), викликається метод untreeify().

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

Відповідь: Пошук вузла в TreeNode.find() організований наступним чином:

Порівнюються перемішані геші: якщо hash < current.hash — ідемо вліво, інакше вправо;
Якщо геші рівні, перевіряється k == key || key.equals(k). При збігу вузол знайдено;
Якщо геші рівні, але equals == false, JVM намагається викликати Comparable.compareTo();
Якщо ключ не реалізує Comparable, JVM запускає двосторонній рекурсивний пошук: перевіряє спочатку ліве піддерево, і якщо збіг не знайдено — обходить праве піддерево.

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

❌ «У Java 8 елементи при колізії вставляються на початок списку.»
Правильно: У Java 8+ вставка відбувається строго в хвіст списку (Tail Insertion) для запобігання зацикленню.

❌ «Список завжди перетворюється на дерево при накопиченні 8 елементів.»
Правильно: Тільки якщо місткість таблиці table.length >= 64. При місткості менше ніж 64 викликається resize().

❌ «Treeification робить HashMap потокобезпечною.»
Правильно: Червоно-чорне дерево не захищає від стану гонки (Data Races). HashMap залишається непотокобезпечною.