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