Що таке колізія в HashMap

Колізія не є помилкою або збоєм. Вона математично неминуча, оскільки множина можливих об'єктів у пам'яті нескінченна, а розмір масиву кошиків суворо обмежений (за замовчуванням...

🟢 Junior Level

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

Колізія в HashMap — це штатна ситуація, за якої два логічно різні ключі (k1.equals(k2) == false) у результаті обчислень претендують на розміщення в одному й тому самому кошику (комірці внутрішнього масиву table[index]).

Колізія не є помилкою або збоєм. Вона математично неминуча, оскільки множина можливих об’єктів у пам’яті нескінченна, а розмір масиву кошиків суворо обмежений (за замовчуванням 16). Для вирішення колізій HashMap використовує метод ланцюжків (Separate Chaining): конфліктуючі елементи вишиковуються в однозв’язний список усередині кошика. Починаючи з Java 8, якщо довжина ланцюжка в кошику досягає 8 елементів (при розмірі таблиці не менше ніж 64), список трансформується в червоно-чорне дерево, захищаючи систему від втрати продуктивності.

Два типи колізій: Колізія Гешів vs Колізія Індексів

Тип колізії	Що сталося	Приклад	Як часто трапляється
Колізія `hashCode()` (Hash Collision)	Два різні об’єкти повернули абсолютно однаковий 32-бітний `int`	`"Aa".hashCode() == 2112` `"BB".hashCode() == 2112`	Рідко (при якісній реалізації геш-функції)
Колізія індексів (Bucket / Slot Collision)	Геш-коди в об’єктів різні, але операція `(n - 1) & hash` дала однаковий індекс комірки	`hash1 = 100` (`...01100100_b`) `hash2 = 116` (`...01110100_b`) Індекс при $n=16$: 4	Постійно (найпоширеніший вид колізії)

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

import java.util.HashMap;

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

        // 1. Справжня колізія hashCode():
        // В алгоритмі String.hashCode() рядки "Aa" і "BB" дають один і той самий результат: 2112
        System.out.println("Aa hash: " + "Aa".hashCode()); // 2112
        System.out.println("BB hash: " + "BB".hashCode()); // 2112

        map.put("Aa", "FirstValue");
        map.put("BB", "SecondValue"); // Потрапляє в той самий кошик, що й "Aa"!

        // Обидва значення успішно зберігаються і коректно витягуються:
        System.out.println("Aa -> " + map.get("Aa")); // FirstValue
        System.out.println("BB -> " + map.get("BB")); // SecondValue

        // 2. Колізія індексів (різні геші, але один бакет):
        // Рядки "FB" (hashCode = 2236) і "Ea" (hashCode = 2236)
        // Будь-які ключі з однаковими молодшими бітами ділять один бакет
        System.out.println("Розмір мапи: " + map.size()); // 2
    }
}

🟡 Middle Level

Математична неминучість колізій

Чому навіть при ідеальному коді колізії гарантовано виникають:

1. Принцип Діріхле (Pigeonhole Principle):

Діапазон типу int в Java обмежений $2^{32} \approx 4\,294\,967\,296$ значеннями. Кількість же можливих рядкових об’єктів навіть довжиною до 10 символів перевищує $10^{15}$. Неможливо відобразити нескінченну множину об’єктів у скінченний 32-бітний адресний простір без дублікатів.

2. Парадокс днів народження (Birthday Paradox):

Теорія ймовірностей стверджує: у групі лише з 23 осіб ймовірність того, що у двох збіжиться день народження (усього 365 варіантів), перевищує 50%.
У HashMap з початковою місткістю $n = 16$ кошиків ймовірність виникнення хоча б однієї колізії перевищує 50% уже при додаванні лише 5 елементів!

Як `HashMap` знаходить потрібний елемент серед колізій

Коли в одному кошику знаходиться кілька елементів, виклик map.get(key) ітерується зв’язним списком або деревом, виконуючи двоетапну перевірку для кожного вузла:

// Вихідний код HashMap HotSpot:
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
    return p;

Перевірка за кешованим гешем: порівнюється примітив p.hash == hash. Якщо перемішані геші не збігаються, вузол відкидається за 1 такт процесора.
Перевірка за посиланням: (k = p.key) == key. Якщо посилання вказують на ту саму адресу в Heap, equals() навіть не викликається.
Перевірка за equals(): тільки якщо геші збіглися, але посилання різні, викликається глибоке доменне порівняння key.equals(k).

🔴 Senior Level

Вплив колізій на апаратну продуктивність (Memory Wall & Cache Misses)

З погляду архітектури сучасних процесорів (CPU Caching), колізії викликають колосальну деградацію затримки (Latency):

Без колізії (O(1)):
CPU ──► table[i] ──► Direct Hit (L1/L2 Cache) ──► Повернення значення (~1 нс)

При глибокій колізії (O(n)):
CPU ──► table[i] ──► Node 1 ──(Pointer Chasing)──► Node 2 ──(RAM)──► Node 3...
   (Промахи кешу L1/L2/L3, завантаження ліній кешу з RAM, виклики virtual equals) (~50-100 нс)

Кожен вузол Node алокується збирачем сміття в довільному місці купи. Обхід зв’язного списку колізій — це класичний Pointer Chasing (гонитва за вказівниками), який не піддається апаратному префетчеру процесора (CPU Hardware Prefetcher), призводячи до постійних затримок на очікування шини оперативної пам’яті.

Атака Hash Flooding DoS та захист через Treeification

Наприкінці 2011 року дослідники інформаційної безпеки продемонстрували вразливість більшості вебсерверів: передача HTTP POST запиту з 10 000 параметрів форми, чиї рядкові імена генерували однаковий hashCode().

Механіка DoS-атаки в Java 7:

У Java 7 вирішення колізій будувалося строго на зв’язних списках;
Додавання $N$ елементів в один бакет вимагало $O(N)$ перевірок на кожному кроці, перетворюючи вставку пачки параметрів на складність $O(N^2)$;
Один HTTP-запит розміром у кілька сотень кілобайтів підвішував ядро CPU сервера на десятки секунд.

Рішення в Java 8+:

При досягненні порогу у 8 елементів список перебудовується в червоно-чорне дерево. Складність вставки та пошуку падає з $O(N)$ до $O(\log N)$, а сумарна обробка DoS-запиту займає $O(N \log N)$ замість $O(N^2)$, нейтралізуючи вектор атаки.

Алгоритм упорядкування вузлів у `TreeNode`: `Comparable` та `tieBreakOrder`

Червоно-чорне дерево вимагає строгого порядку елементів ($<$ або $>$). Як HashMap упорядковує вузли, якщо їхній hash повністю збігається?

Інтерфейс Comparable:
Якщо клас ключа реалізує Comparable<K> (як, наприклад, String, Integer, UUID), вузли порівнюються викликом ((Comparable)k).compareTo(x).
Fallback через tieBreakOrder:
Якщо ключі не реалізують Comparable або їхній compareTo() повернув 0 (але за equals() вони не рівні), HashMap використовує метод tieBreakOrder():
```
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;
}
```
Як фінальний арбітр використовується System.identityHashCode() (вихідний нативний геш об’єкта з його Mark Word).

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

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

Колізія в HashMap — це ситуація, коли різні ключі (equals == false) потрапляють в один бакет. Буває двох видів: збіг hashCode() (рідко) або збіг індексу (n - 1) & hash (постійно). Колізії неминучі через принцип Діріхле та парадокс днів народження (при $n=16$ колізія ймовірніша за 50% вже при 5 ключах). Для вирішення застосовується метод ланцюжків: елементи зв’язуються у список ($O(k)$), а при 8+ елементах і таблиці $\ge 64$ конвертуються в червоно-чорне дерево ($O(\log k)$), що захищає систему від Hash Flooding DoS атак.

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

Питання 1: У чому принципова різниця між колізією геш-кодів (`hashCode collision`) та колізією кошиків (`bucket collision`), і яка трапляється частіше?

Відповідь:

Колізія hashCode(): два різні об’єкти повертають однаковий 32-бітний int із методу hashCode(). Відбувається рідко, якщо геш-функція враховує всі значущі поля об’єкта.
Колізія кошиків: два об’єкти мають різні 32-бітні hashCode(), але при накладанні бітової маски (table.length - 1) & hash їхні молодші біти збіглися, вказавши на один індекс масиву.
Колізія кошиків трапляється на порядки частіше, оскільки місткість масиву таблиці (16, 32, 64) багаторазово менша за діапазон чисел $2^{32}$.

Питання 2: Як парадокс днів народження пояснює виникнення колізій задовго до того, як таблиця заповниться до порогу ресайзу?

Відповідь: Багато хто помилково вважає, що колізії починаються тільки при заповненні таблиці ближче до threshold (12 елементів із 16). Відповідно до теорії ймовірностей та парадоксу днів народження, ймовірність відсутності колізій при додаванні $k$ елементів у $n$ кошиків дорівнює: $P(\text{no collisions}) = \prod_{i=1}^{k-1} \left(1 - \frac{i}{n}\right)$ Для таблиці з 16 кошиків при $k = 5$ ймовірність виникнення хоча б однієї колізії становить уже $\approx 51\%$. Колізії — нормальний стан таблиці з перших секунд її наповнення.

Питання 3: Що станеться при колізії 8 елементів, якщо клас ключа НЕ реалізує інтерфейс `Comparable`?

Відповідь: Дерево TreeNode все одно буде успішно побудоване. HashMap спробує знайти метод comparableClassFor(key). Якщо ключ не реалізує Comparable, при вставці в дерево JVM спочатку спробує рекурсивно обійти обидві гілки вузла, а в спірних випадках застосує метод tieBreakOrder(): порівняє імена класів об’єктів, а при їхньому збігу впорядкує вузли за нативною адресою пам’яті через System.identityHashCode(). Проте накладні витрати на балансування дерева без Comparable будуть вищими.

Питання 4: Як зловмисник організовує атаку Hash Flooding DoS, і як Java 8 гарантує стійкість застосунку?

Відповідь: Зловмисник генерує тисячі рядків з однаковим hashCode() (в алгоритмі Java s[0]*31^(n-1) + ... колізії підбираються тривіально, наприклад, перестановкою пар "Aa" і "BB"). Відправивши форму з 20 000 таких параметрів, він заганяє всі елементи в один бакет вебсервера. У Java 7 пошук і вставка елементів у список відбувалися за $O(n)$, перетворюючи парсинг запиту на квадратичну складність $O(n^2)$ зі 100% блокуванням ядра процесора. У Java 8+ список деревофікується в червоно-чорне дерево, знижуючи складність до $O(n \log n)$, що дозволяє серверу обробити запит за мілісекунди.

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

❌ «Колізія означає, що розробник припустився помилки в hashCode().»
Правильно: Навіть при еталонному hashCode() колізії неминучі через проєкцію 32-бітного гешу на невеликий масив кошиків (принцип Діріхле).

❌ «Якщо в HashMap сталася колізія, старий елемент перезаписується новим.»
Правильно: Перезапис значення відбувається тільки тоді, коли збіглися і геш, і equals(). При колізії (equals == false) обидва елементи зберігаються в одному кошику.

❌ «При колізіях HashMap завжди працює за $O(n)$.»
Правильно: У Java 8+ при зростанні ланцюжка понад 8 елементів бакет трансформується в дерево, гарантуючи верхню межу складності $O(\log n)$.