Как 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 остается непотокобезопасной.