🟢 Junior Level

Колізія — це коли два різні ключі потрапляють в одну й ту саму корзину (бакет) в HashMap.

Це НЕ помилка! Це очікувана поведінка. Як у школі два учні можуть мати одне прізвище — це не означає, що вони одна людина. HashMap розрахована на колізії і вміє їх обробляти.

Це відбувається тому, що кількість можливих ключів нескінченна, а кількість корзин обмежена. Уявіть парковку на 16 місць: якщо приїдуть 20 машин, щонайменше на 4 місця претендують по 2 машини.

Приклад колізії:

HashMap<String, String> map = new HashMap<>();
map.put("Aa", "value1");  // hashCode = 2112
map.put("BB", "value2");  // hashCode = 2112 (такий самий!)

// Чому: формула String.hashCode(): s[0]*31^(n-1) + s[1]*31^(n-2)
// "Aa": 65*31 + 97 = 2112
// "BB": 66*31 + 66 = 2112
// Різні символи, але математично дають той самий результат
// Обидва потрапили в одну корзину — це колізія

Хороша новина: HashMap вміє обробляти колізії — вона зберігає кілька елементів в одній корзині у вигляді ланцюжка.

🟡 Middle Level

Чому колізії неминучі

1. Принцип Діріхле: Хеш-кодів 2^32 (~4.3 млрд), а можливих об’єктів — нескінченно
2. Парадокс днів народження: У таблиці на 365 бакетів ймовірність колізії > 50% вже при 23 елементах
3. Стиснення діапазону: Навіть різні hashCode можуть співпасти після & (n-1)

Типи колізій

Тип колізії	Причина	Рішення
Колізія hashCode	Два об’єкти мають однаковий hashCode() (рідко при хорошій функції)	Treeification при 8 елементах (Java 8+)
Колізія індексу	hashCode РІЗНІ, але (n-1) & hash однаковий (набагато частіше)	Resize (подвоєння таблиці)

Приклад колізії індексу: hashCode = 100 і hashCode = 116 при n=16 обидва дають індекс 4, тому що 100 & 15 = 4 і 116 & 15 = 4.

Стратегії розв’язання

• Separate Chaining (метод ланцюжків) — використовується в HashMap, LinkedHashMap, ConcurrentHashMap
• Open Addressing (відкрита адресація) — використовується в ThreadLocalMap, IdentityHashMap

Еволюція

Версія	Структура	Складність
Java 7	Зв’язний список	O(n)
Java 8+	Список → Дерево	O(log n)

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

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

🔴 Senior Level

Internal Mechanics

Колізія визначається на рівні бакета:

// hash(k1) & (n-1) == hash(k2) & (n-1)
// Але k1.equals(k2) == false

HashMap використовує дворівневу фільтрацію:

1. Швидкий відсів — порівняння за хешем (p.hash == hash), відсіває 99.9%
2. Точна перевірка — виклик equals() для решти кандидатів

Treeification Details

При 8 елементах в бакеті:

• Якщо capacity < 64: викликається resize() (рознесе елементи)
• Якщо capacity >= 64: список → червоно-чорне дерево

Чому 8? Ймовірність ланцюжка з 8 елементів при loadFactor 0.75 і хорошому hashCode: 0.00000006 (розподіл Пуассона). Це маркер аномалії — або поганий hashCode, або атака.

CPU і Cache Impact

Колізії впливають на продуктивність сильніше, ніж здається:

• Кожен equals() — це виклик методу + порівняння полів
• Ноди розкидані по Heap → Cache Miss при кожному переході
• При treeification додається overhead балансування дерева

Hash Flooding Attack

Цілеспрямована DoS-атака:

1. Зловмисник генерує ключі з однаковим хешем
2. Всі елементи потрапляють в один бакет
3. Java 7: O(n²) при вставці n елементів → 100% CPU
4. Java 8+: O(n log n) — атака пом’якшена, але не усунена повністю

Memory Implications

Кожна колізія = додатковий об’єкт Node в Heap. При масових колізіях:

• Зростає тиск на Young Gen GC
• При treeification: TreeNode ~ 2x розмір Node
• В Old Gen накопичуються довгоживучі ноди

Production Monitoring

Для виявлення проблем:

• Моніторинг часу get/put — зростання вказує на колізії
• Аналіз розподілу бакетів через JFR (Java Flight Recorder)
• Перевірка якості hashCode() через unit-тести на розподіл

---

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

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

• Колізія = два різні ключі потрапили в один бакет — це нормально, не помилка
• Принцип Діріхле: ключів нескінченно багато, бакетів обмежено — колізії неминучі
• Java 7: O(n) при колізіях, Java 8+: O(log n) завдяки treeification
• Парадокс днів народження: при 5 елементах і 16 бакетах ймовірність колізії > 50%
• Класичний приклад: “Aa” і “BB” мають однаковий hashCode = 2112
• Два типи колізій: однаковий hashCode І різні hashCode, але однаковий індекс після (n-1) & hash
• Поріг 8 обрано на основі розподілу Пуассона — ймовірність ≈ 0.00000006

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

• Чому колізії неминучі? — hashCode = 32 біти (~4.3 млрд), а можливих об’єктів нескінченно
• Чим Separate Chaining відрізняється від Open Addressing? — chaining = списки в бакетах, open addressing = пошук наступного вільного
• Що таке Hash Flooding Attack? — зловмисник підбирає ключі з однаковим хешем → DoS
• Чому ймовірність 8 колізій така мала? — розподіл Пуассона при loadFactor 0.75

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

• «Колізія — це баг» — ні, очікувана поведінка
• «HashMap не підтримує колізії» — підтримує через ланцюжки/дерева
• «hashCode завжди унікальний» — ні, 32 біти не можуть покрити нескінченну множину

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

• [[3. Як HashMap визначає, в який bucket покласти елемент]]
• [[5. Як HashMap обробляє колізії]]
• [[6. Що відбувається при досягненні 8 елементів в одному bucket]]
• [[9. Якщо два об’єкти мають однаковий hashCode(), чи обов’язково вони рівні за equals()]]