🟢 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 вставка в голову списка при resize меняла порядок элементов на обратный. В многопоточной среде это создавало циклические ссылки (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 в многопоточной среде]]