Как устроена HashMap внутри

Внутри HashMap состоит из массива корзин (Node[] table), размер которого всегда равен степени двойки ($16, 32, 64\dots$). При добавлении пары по ключу вычисляется его хеш-к...

🟢 Junior Level

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

HashMap — это ассоциативный массив (структура «ключ-значение»), в основе которого лежит хеш-таблица с открытым хешированием и методом цепочек (Separate Chaining).

Внутри HashMap состоит из массива корзин (Node<K,V>[] table), размер которого всегда равен степени двойки ($16, 32, 64\dots$). При добавлении пары по ключу вычисляется его хеш-код, который преобразуется в индекс массива с помощью быстрой битовой маски: index = (n - 1) & hash. Если ячейка свободна, туда записывается узел Node. При возникновении коллизии (два разных ключа попали в один индекс) элементы организуются в односвязный список. Начиная с Java 8, если длина списка в одной корзине достигает 8 элементов, а общий размер таблицы не менее 64, список трансформируется в сбалансированное красно-черное дерево (TreeNode), что гарантирует скорость поиска $O(\log n)$ даже при катастрофическом количестве коллизий.

Сравнительная таблица структур Map в Java

Реализация Map	Внутренняя структура	Временная сложность	Гарантия порядка элементов	Потокобезопасность
`HashMap`	Массив + списки + красно-черные деревья	$O(1)$ в среднем, $O(\log n)$ в худшем	❌ Нет порядка	❌ Нет (Fail-Fast)
`LinkedHashMap`	Хеш-таблица + двусвязный список нод	$O(1)$	✅ Порядок вставки (или доступа)	❌ Нет
`TreeMap`	Красно-черное дерево (Red-Black Tree)	$O(\log n)$ всегда	✅ По ключу (`Comparable`/`Comparator`)	❌ Нет
`ConcurrentHashMap`	Массив бакетов + CAS + `synchronized` на ноду	$O(1)$	❌ Нет порядка	✅ Да (Thread-safe)

Базовый пример на Java 21

import java.util.HashMap;
import java.util.Map;

public class HashMapBasicsDemo {
    public static void main(String[] args) {
        // Конструктор по умолчанию: capacity = 16, loadFactor = 0.75
        // Важно: до первого put() массив table равен null (ленивая аллокация памяти)!
        Map<String, Integer> userAges = new HashMap<>();

        // 1. Добавление элементов (put)
        userAges.put("Alice", 30); // Хеш ключа -> вычисление индекса -> запись ноды
        userAges.put("Bob", 25);
        userAges.put(null, 99);    // null-ключ всегда попадает в table[0]

        // 2. Получение элемента (get)
        System.out.println("Возраст Alice: " + userAges.get("Alice")); // O(1)

        // 3. Перезапись значения (при совпадении hash и equals)
        userAges.put("Alice", 31); // Заменяет 30 на 31, возвращает старое значение 30

        System.out.println("Размер мапы: " + userAges.size());
    }
}

🟡 Middle Level

Жизненный цикл операции `put(key, value)`

Алгоритм вставки элемента в HashMap в OpenJDK HotSpot состоит из следующих последовательных шагов:

                  put(key, value)
                         │
                         ▼
             key == null ? hash = 0 
        : hash = (h = key.hashCode()) ^ (h >>> 16)
                         │
                         ▼
               table == null или пуст?
              ├── Да ──► Вызов resize() (аллокация массива 16)
              └── Нет
                         │
                         ▼
             index = (table.length - 1) & hash
                         │
                         ▼
                  table[index] == null?
         ├── Да ──► Создать Node<K,V> и положить в ячейку
         └── Нет (КОЛЛИЗИЯ!)
                         │
                         ▼
             Первый узел совпал по ключу?
     (p.hash == hash && (p.key == key || key.equals(p.key)))
         ├── Да ──► Перезаписать value
         └── Нет ──► Проверить тип узла:
                      ├── TreeNode ──► Вставка в красно-черное дерево
                      └── Node (Список) ──► Итерация до конца списка:
                             ├── Ключ найден ──► Обновить value
                             └── Достигнут конец ──► Вставить в хвост
                                        │
                                        ▼
                            Длина цепочки >= 8?
                          ├── Да ──► treeifyBin() (дерево или resize)
                          └── Нет ──► Завершить
                         │
                         ▼
        Инкремент modCount и size; size > threshold?
              ├── Да ──► Вызов resize() (удвоение capacity)
              └── Нет ──► Завершить

Почему размер таблицы всегда степень двойки ($2^n$)

В исходном коде HashMap индекс корзины вычисляется по формуле:

int index = (n - 1) & hash;

где $n$ — текущая емкость таблицы (table.length).

Математическая причина:

Замена деления битовой маской: в математике операция остатка от деления $hash \pmod n$ на произвольное число требует сложной и медленной инструкции целочисленного деления CPU (idiv, занимающей 20–40 тактов процессора). Если $n$ строго является степенью двойки ($2^k$), то $hash \pmod{2^k}$ математически эквивалентен побитовой операции AND с числом $(2^k - 1)$, которая выполняется процессором за 1 такт.
Равномерность маски: если $n = 16$ (0001 0000_b), то $n - 1 = 15$ (0000 1111_b). Младшие 4 бита маски состоят из одних единиц. Это гарантирует, что каждый младший бит хеша будет определять итоговый индекс. Если бы емкость была нечетным или произвольным числом (например, 15, маска 14 = 1110_b), младший бит индекса всегда был бы 0, и все нечетные корзины таблицы никогда бы не заполнились.

Функция битового перемешивания (Hash Perturbation Function)

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

Зачем нужен сдвиг `h >>> 16` и XOR:

У стандартного объекта hashCode() возвращает 32-битный int. При малом размере мапы (например, $n = 16$) маска (n - 1) = 15 учитывает только последние 4 младших бита. Старшие 28 бит хеш-кода в определении индекса никак не участвуют!
Если у группы объектов младшие биты хешей случайно совпадают (а старшие различаются), они все попадут в одну корзину, образовав чудовищную коллизию.
Операция (h ^ (h >>> 16)) «подмешивает» старшие 16 бит хеша в младшие. В результате изменение любого бита исходного 32-битного хеша влияет на выбор корзины.

🔴 Senior Level

HotSpot Memory Layout: Накладные расходы памяти

В корпоративных Highload-приложениях миллионы записей в HashMap создают колоссальное давление на кучу (Heap) из-за накладных расходов памяти:

Анатомия `Node<K, V>` в 64-битной JVM с Compressed OOPs (`-XX:+UseCompressedOops`):

Object Header: 12 байт (Mark Word 8 байт + Compressed Klass Pointer 4 байта);
int hash: 4 байта;
final K key: 4 байта (сжатая ссылка);
V value: 4 байта (сжатая ссылка);
Node<K,V> next: 4 байта (сжатая ссылка на следующий элемент списка);
Padding (выравнивание по 8 байт): 4 байта.
Итого: ровно 32 байта памяти только на оболочку одного узла Node (без учета самих объектов ключа и значения)!

Анатомия `TreeNode<K, V>`:

TreeNode расширяет LinkedHashMap.Entry, содержа ссылки parent, left, right, prev и поле boolean red. Его размер составляет 56–64 байта (в 2 раза тяжелее списка).

Математика ресайза в Java 8+: Bitwise Splitting без перехеширования

В Java 7 при увеличении емкости таблицы (resize()) происходил полный пересчет индексов каждого элемента через hash % newCapacity со вставкой в начало связного списка (что вызывало зацикливание потоков в многопоточной среде).

В Java 8+ алгоритм кардинально переписан: при удвоении емкости ($oldCap \to 2 \times oldCap$) в маске появляется ровно один новый значащий бит на позиции $oldCap$.

oldCap = 16  (Маска: 0000 1111)
newCap = 32  (Маска: 0001 1111)
Разница в масках — это бит 16 (0001 0000)

JVM проверяет единственный бит: (e.hash & oldCap) == 0:

Если равен 0, индекс элемента в новой таблице не изменяется (newIndex = oldIndex);
Если равен 1, элемент смещается ровно на величину старой емкости: newIndex = oldIndex + oldCap.

// Из исходного кода HashMap.resize():
Node<K,V> loHead = null, loTail = null; // Цепочка для старого индекса
Node<K,V> hiHead = null, hiTail = null; // Цепочка для индекса (oldIndex + oldCap)
do {
    next = e.next;
    if ((e.hash & oldCap) == 0) {
        if (loTail == null) loHead = e;
        else loTail.next = e;
        loTail = e;
    } else {
        if (hiTail == null) hiHead = e;
        else hiTail.next = e;
        hiTail = e;
    }
} while ((e = next) != null);

Элементы разделяются на две очереди с сохранением оригинального порядка (Tail Insertion), исключая бесконечные циклы.

Распределение Пуассона и константа древофикации 8

Почему для превращения списка в дерево выбран порог TREEIFY_THRESHOLD = 8?

В документации OpenJDK к классу HashMap приводится строгий математический расчет на основе теории вероятностей. При идеальной хеш-функции и коэффициенте загрузки $0.75$ распределение элементов по корзинам подчиняется распределению Пуассона со средним параметром $\lambda \approx 0.5$:

\[P(k) = \frac{e^{-\lambda} \lambda^k}{k!}\]

Вероятность образования корзины с $k$ элементами:

0 элементов: $0.6065$
1 элемент: $0.3032$
2 элемента: $0.0758$
3 элемента: $0.0126$
…
8 элементов: $0.00000006$ ($6 \times 10^{-8}$)

Вероятность коллизии глубиной 8 при честном hashCode() составляет менее одной стомиллионной доли процента. Деревья были добавлены исключительно как эшелонированная защита от преднамеренных атак Hash Flooding DoS, когда злоумышленник специально генерирует ключи с одинаковыми хешами для деградации производительности сервера до $O(n)$.

🎯 Шпаргалка для интервью

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

HashMap — это хеш-таблица на основе массива корзин (Node<K,V>[] table), размер которой всегда кратен степени двойки. Индекс определяется битовой операцией (n - 1) & hash, где hash получен смешиванием старших и младших 16 бит исходного hashCode(). Коллизии разрешаются методом цепочек. Если длина цепочки достигает 8, а размер массива $\ge 64$, список перестраивается в красно-черное дерево ($O(\log n)$). При ресайзе массив удваивается, а элементы разделяются на старый и новый (oldIndex + oldCap) бакеты проверкой одного бита (hash & oldCap). HashMap не потокобезопасна.

2. 4 каверзных вопроса с глубокими ответами

Вопрос 1: Почему при достижении 8 элементов в корзине дерево создается не всегда, и какое второе условие обязательно должно выполниться?

Ответ: Для превращения списка в красно-черное дерево (метод treeifyBin()) должны одновременно выполниться два условия:

Длина цепочки в конкретном бакете $\ge 8$ (TREEIFY_THRESHOLD);
Общая емкость массива таблицы table.length $\ge 64$ (MIN_TREEIFY_CAPACITY).
Если в корзине накопилось 8 элементов, но емкость таблицы меньше 64 (например, 16 или 32), превращения в дерево не происходит. Вместо этого вызывается метод resize(), удваивающий массив корзин. Архитекторы JDK исходили из того, что при малой таблице коллизия вызвана просто недостатком корзин, и ресайз распределит элементы эффективнее, чем создание тяжелых объектов TreeNode.

Вопрос 2: Как работает оптимизация разделения бакета (`loHead`/`hiHead`) при ресайзе в Java 8+, и почему она полностью устранила баг бесконечного цикла Java 7?

Ответ: В Java 7 элементы при ресайзе вставлялись в голову нового списка (Head Insertion), что инвертировало порядок элементов. При гонке потоков один поток мог переставить указатели так, что ссылка A.next = B превращалась в кольцо B.next = A, приводя к 100% загрузке CPU при последующем get().
В Java 8+ используется хвостовая вставка (Tail Insertion) и побитовая проверка (e.hash & oldCap) == 0. Список за один проход расщепляется на две независимые связные цепочки (lo — элементы, остающиеся на месте, и hi — элементы, смещающиеся на +oldCap) с полным сохранением исходного порядка элементов, что исключает возникновение циклических ссылок.

Вопрос 3: Зачем в функции `hash()` старшие 16 бит складываются через XOR с младшими (`h ^ (h >>> 16)`)?

Ответ: Массив HashMap по умолчанию имеет небольшой размер (16, 32, 64), поэтому маска (n - 1) оставляет только последние 4–6 младших бит хеша. Если ключи генерируют хеш-коды, у которых меняются только старшие биты (например, числа кратные 1000 или форматированные строковые ID), без сдвига и XOR все такие ключи будут давать нулевой или одинаковый индекс, создавая критические коллизии. XOR со сдвигом на 16 бит гарантирует, что вариативность старших разрядов хеша отразится на младших разрядах, обеспечивая равномерное распределение по корзинам.

Вопрос 4: Почему в качестве порога обратного преобразования дерева в список (`UNTREEIFY_THRESHOLD`) выбрано значение 6, а не 7 или 8?

Ответ: Разница между порогом древофикации (8) и де-древофикации (6) в 2 единицы представляет собой гистерезис (Hysteresis gap). Если бы оба порога были равны (например, 8 для дерева и 7 для списка), то при частой циклической вставке и удалении 8-го элемента структура постоянно совершала бы дорогостоящие перестроения дерева в список и обратно (эффект Flapping / Churning). Зазор в 2 элемента предотвращает частую смену внутренней структуры при небольших колебаниях количества данных.

3. Типичные ошибки и Red Flags

❌ “В HashMap массив создается сразу при вызове new HashMap<>().”
Правильно: Конструктор лишь валидирует loadFactor и initialCapacity. Сам массив table аллоцируется лениво — при первом вызове put() внутри метода resize().

❌ “Индекс корзины вычисляется через остаток от деления hash % capacity.”
Правильно: Используется побитовое AND: (capacity - 1) & hash, что работает на порядки быстрее деления.

❌ “Красно-черное дерево создается всегда, как только в списке появилось 8 элементов.”
Правильно: Только если общая емкость таблицы table.length >= 64. Иначе происходит вызов resize().