Когда происходит rehashing в HashMap

В HashMap процедура resize() инициируется в следующих ключевых ситуациях:

🟢 Junior Level

Rehashing (рехеширование / resize) — это процедура выделения нового массива бакетов увеличенной ёмкости (в 2 раза больше прежней) и перераспределения существующих элементов по новым ячейкам.

В HashMap процедура resize() инициируется в следующих ключевых ситуациях:

Первый вызов put() (ленивая инициализация): При создании new HashMap() массив бакетов не выделяется в памяти (table == null). Память под массив (по умолчанию на 16 ячеек) выделяется только при первой вставке данных.
Превышение порога загрузки (threshold): Когда текущее количество элементов size после очередной вставки превышает значение capacity * loadFactor (по умолчанию $16 \times 0.75 = 12$).
Конфликт коллизий при малой таблице: Если в одном бакете скопилось 8 элементов, но общий размер таблицы меньше 64 (table.length < 64), вместо построения красно-чёрного дерева вызывается resize().

Пример

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

public class RehashingTriggerDemo {
    public static void main(String[] args) {
        // 1. Создание: table == null
        Map<Integer, String> map = new HashMap<>();

        // 2. Первый put: срабатывает resize(), создается table емкостью 16, threshold = 12
        map.put(1, "A");

        // 3. Добавляем элементы до порога 12
        for (int i = 2; i <= 12; i++) {
            map.put(i, "V" + i);
        }

        // 4. Вставка 13-го элемента: условие (++size > threshold) истинно (13 > 12)
        // Срабатывает resize(): capacity удваивается до 32, threshold становится 24
        map.put(13, "V13");
    }
}

Аналогия: Рехеширование похоже на переезд офиса компании в новое здание в два раза больше прежнего. Переезд происходит либо в первый рабочий день (когда офис открывается), либо когда все рабочие места заняты более чем на 75%, чтобы избежать тесноты и очередей в коридорах.

🟡 Middle Level

Все триггеры запуска метода `resize()`

В исходном коде java.util.HashMap (Java 8+) вызов метода resize() происходит в четырех точках:

Триггер	Условие в коде	Что происходит
1. Ленивая инициализация	`tab == null \\|\\| tab.length == 0`	Выделяется начальный массив `Node<K,V>[]` (обычно 16)
2. Превышение порога при `put`	`if (++size > threshold)`	Текущая емкость удваивается ($N \to 2N$), порог пересчитывается
3. Недостаточный размер при трификации	`tab.length < MIN_TREEIFY_CAPACITY (64)`	При 8 коллизиях в бакете вместо дерева удваивается массив таблицы
4. Массовая вставка `putAll()`	`targetCap > threshold` в `putMapEntries()`	Превентивный разовый `resize()` под размер входящей коллекции

Временная стоимость и влияние на Latency

Рехеширование — самая ресурсоемкая операция в жизненном цикле HashMap:

Аллокация памяти: Создается новый массив ссылок удвоенного размера ($O(N)$).
Перенос элементов: Все существующие узлы Node<K,V> сканируются и перелинковываются в новые бакеты ($O(N)$).
Latency Spike: В latency-sensitive сервисах (HighLoad, микросекундный SLA) внезапный resize() на карте из 1 000 000 элементов может вызвать «залипание» потока на 20–100 мс.

Предотвращение ресайза через расчет начальной емкости

Чтобы избежать множественных ресайзов при известном числе элементов, емкость задают заранее:

// До Java 19:
int expectedElements = 10_000;
int initialCapacity = (int) Math.ceil(expectedElements / 0.75f);
Map<String, User> map = new HashMap<>(initialCapacity);

// Начиная с Java 19:
Map<String, User> modernMap = HashMap.newHashMap(expectedElements);

🔴 Senior Level

Глубокий анализ исходного кода триггеров

1. Пост-инкрементный триггер в `putVal`

В Java 8+ проверка порога выполняется после того, как новый узел уже успешно добавлен в бакет:

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    // ... логика поиска и вставки узла ...
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

Важное отличие от Java 7: В Java 7 проверка была предварительной (if (size >= threshold && null != table[bucketIndex])). В Java 8+ сначала увеличивается счетчик size, и если он строго превысил threshold, вызывается resize().

2. Триггер из `treeifyBin`

Когда в результате коллизий длина связного списка в отдельной корзине достигает TREEIFY_THRESHOLD = 8, вызывается метод treeifyBin:

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) // MIN_TREEIFY_CAPACITY = 64
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        // Полноценная конвертация связного списка в TreeNode (RB-Tree)
    }
}

Архитектурное решение HotSpot: Превращение связного списка в красно-чёрное дерево увеличивает расход памяти (каждый TreeNode занимает 56 байт вместо 32 байт у Node). Если вся таблица еще маленькая (например, 16 или 32 бакета), коллизия из 8 элементов чаще вызвана неудачным модулем (n-1) & hash, а не патологией хеш-функции. Поэтому JVM предпочитает сначала удвоить массив бакетов: при ресайзе с 32 до 64 бит маски сместится, и длинная цепочка с высокой вероятностью распадется на две короткие!

3. Превентивный триггер в `putMapEntries` (`putAll`)

При добавлении другой коллекции через конструктор new HashMap<>(Map m) или метод map.putAll(m):

final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    int s = m.size();
    if (s > 0) {
        if (table == null) { // Если таблица еще пустая
            float ft = ((float)s / loadFactor) + 1.0F;
            int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY);
            if (t > threshold)
                threshold = tableSizeFor(t);
        } else {
            // Если таблица уже инициализирована и элементов больше порога
            while (s > threshold && table.length < MAXIMUM_CAPACITY)
                resize();
        }
    }
    // далее в цикле последовательные putVal
}

HashMap заранее резервирует нужный размер, избегая десятков каскадных перестроений в цикле.

Почему именно геометрическое удвоение ($2 \times$)?

Если бы при ресайзе массив увеличивался на фиксированное число ячеек (арифметическая прогрессия, например, $+16$), то добавление $N$ элементов потребовало бы $\frac{N}{16}$ ресайзов, что привело бы к квадратичной сложности вставки $O(N^2)$. Удвоение размера ($2 \times$) обеспечивает амортизированную сложность $O(1)$ на операцию put, так как суммарное число копирований при вставке $N$ элементов представляет собой сумму геометрической прогрессии $1 + 2 + 4 + 8 + \dots + N \le 2N$, что дает константную стоимость на один элемент.

4 Tricky Questions

1. В какой момент происходит `resize()` при превышении порога — до или после фактической вставки нового элемента?

Ответ: В Java 8+ вызов resize() происходит после физической вставки нового элемента в таблицу (код: if (++size > threshold) resize();). В Java 7 логика была обратной: resize() выполнялся до добавления элемента и только при выполнении двух условий: size >= threshold И в бакете, куда планировалась вставка, уже был хотя бы один элемент (null != table[bucketIndex]). Если бакет был пуст, Java 7 позволяла вставить элемент без ресайза, даже если size >= threshold.

2. Сколько раз вызовется `resize()`, если в пустую `new HashMap<>()` добавить 10 000 элементов через `putAll()`?

Ответ: Ровно 1 раз. При передаче коллекции в пустую HashMap срабатывает метод putMapEntries. В ветке if (table == null) он вычисляет: $t = \text{tableSizeFor}\left(\left\lceil \frac{10000}{0.75} \right\rceil + 1\right) = \text{tableSizeFor}(13334 + 1) = 16384$ Значение threshold сразу устанавливается в 16384. Затем при вставке первого элемента в цикле метод resize() вызывается единственный раз и сразу инициализирует массив table на 16 384 ячейки. Все 10 000 элементов будут вставлены без единого дополнительного ресайза.

3. Может ли случиться так, что в бакете скопилось 12 элементов, но бакет всё ещё остаётся связным списком и не стал деревом?

Ответ: Да, может. Это происходит, если capacity таблицы меньше 64. Например, если начальная емкость таблицы равна 16, и все добавляемые ключи имеют одинаковый хеш-код (жесткая коллизия):

При 8-м элементе сработает условие tab.length < 64 $\to$ ресайз до 32.
При 9-м, 10-м элементах коллизия сохраняется. При достижении пороговых условий снова сработает ресайз до 64.
До тех пор, пока tab.length < 64, treeifyBin будет вызывать resize() вместо трификации, и элементы останутся в связном списке Node. Только когда размер таблицы достигнет 64, этот бакет окончательно конвертируется в красно-чёрное дерево TreeNode.

4. Если из `HashMap` с 1 000 000 элементов удалить 999 999 элементов через `remove()`, произойдет ли обратное рехеширование (Shrinking)?

Ответ: Нет, никогда. В java.util.HashMap отсутствует механизм сжатия массива бакетов (downsizing / shrinking). Массив table останется размером более 1 миллиона ячеек (ближайшая степень двойки — $1\,048\,576$), занимая около 4–8 МБ памяти под пустые ссылки. Если требуется освободить эту память, необходимо вручную создать новый экземпляр new HashMap<>(map) и отдать старый на откуп сборщику мусора (GC).

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

Когда происходит Resize:
1. Первый put (Lazy Init с 0 до 16).
2. ++size > threshold (после вставки очередного элемента).
3. Длина бакета $\ge 8$, но table.length < 64 (ресайз вместо дерева).
4. Превентивно в putAll() под размер передаваемой коллекции.
Сложность: $O(N)$ по времени и памяти. Создается новый массив удвоенного размера ($2 \times$).
Геометрическая прогрессия: Удвоение обеспечивает амортизированную сложность вставок $O(1)$.
Удаление элементов: HashMap никогда не сжимает массив table обратно при вызовах remove().
Latency Spikes: В высоконагруженных системах ресайз в runtime недопустим — инициализируйте размер заранее (HashMap.newHashMap(expected)).

🟢 Junior Level

Пример

🟡 Middle Level

Все триггеры запуска метода resize()

Временная стоимость и влияние на Latency

Предотвращение ресайза через расчет начальной емкости

🔴 Senior Level

Глубокий анализ исходного кода триггеров

1. Пост-инкрементный триггер в putVal

2. Триггер из treeifyBin

3. Превентивный триггер в putMapEntries (putAll)