🟢 Junior Level

При rehashing HashMap создаёт новый массив в 2 раза больше и переносит туда все элементы.

Простой пример:

HashMap<String, Integer> map = new HashMap<>(); // 16 бакетов
// Добавляем 13 элементов...
// Срабатывает resize:
// 1. Создаётся новый массив на 32 бакета
// 2. Все 13 элементов переносятся в новые бакеты
// 3. Старый массив удаляется

Аналогия: У вас был шкаф с 16 полками, и он переполнился. Вы покупаете шкаф на 32 полки и переставляете все вещи. Некоторые вещи остаются на тех же полках, а некоторые переезжают на новые.

Главное: Resize — медленная операция O(n). Лучше избегать её, заранее задав правильный размер.

🟡 Middle Level

Битовый трюк: (hash & oldCap)

Поскольку capacity всегда степень двойки, при удвоении к маске добавляется один бит:

Старая маска (15): 0000 1111
Новая маска (31):  0001 1111
                   ^
                   Новый бит = oldCap

Проверка одного бита определяет судьбу элемента:

if ((e.hash & oldCap) == 0) {
    // Остаётся на старом индексе
} else {
    // Перемещается на oldIndex + oldCapacity
}

Формирование списков Lo и Hi

При обходе одного бакета HashMap создаёт два временных списка:

• Lo List: элементы, остающиеся на месте
• Hi List: элементы, перемещающиеся на index + oldCap

Сохранение порядка (Java 8+)

В Java 8 используется Tail Insertion — порядок элементов сохраняется. Это предотвращает зацикливание linked list (проблема Java 7). Однако HashMap всё ещё НЕ потокобезопасна — при конкурентном resize возможна потеря элементов. Для многопоточного доступа используйте ConcurrentHashMap.

Перенос деревьев

Если бакет — дерево:

1. Дерево разделяется на Lo и Hi части
2. Если в части <= 6 элементов → untreeify (обратно в список)
3. Если > 6 → новое дерево в новом бакете

Накладные расходы

Ресурс	Стоимость
Память	Два массива одновременно (старый + новый)
CPU	O(n) — проход по всем элементам
GC	Давление от временных объектов и старого массива

🔴 Senior Level

Алгоритм resize в Java 8+:

1. Создаём новый массив размером 2x от старого
2. Для каждого бакета делим элементы на две группы по одному биту hash:
   • Lo (bit = 0): остаются на том же индексе
   • Hi (bit = 1): перемещаются на index + oldCap
3. Старый массив = null для GC

Почему это эффективно: не нужно пересчитывать hashCode — достаточно проверить ОДИН бит (hash & oldCap). Элементы либо остаются на месте, либо сдвигаются на фиксированное смещение.

TreeNode.split()

При разделении дерева:

// Если в части <= UNTREEIFY_THRESHOLD (6) — untreeify
if (lc <= UNTREEIFY_THRESHOLD)
    tab[index] = loHead.untreeify(map);
else {
    tab[index] = loHead;
    if (hiHead != null) loHead.treeify(tab); // Ребалансировка
}

Memory Pressure

При resize capacity=1M → capacity=2M:

• Новый массив: ~16MB (1M ссылок × 8 байт × 2 за счёт UseCompressedOops)
• Старый массив: ещё ~16MB до GC
• В пике: +32MB в Heap

GC Impact

• Старый массив → сразу мусор (Young/Middle Gen)
• Перераспределение ссылок → write barriers для GC
• В G1: может вызвать mixed GC, если старый массив в Old Gen

ConcurrentHashMap: Parallel Resize

В ConcurrentHashMap resize выполняется параллельно:

• Несколько потоков могут помогать переносить элементы
• Используется transferIndex для координации
• ForwardingNode указывает на прогресс

Production Experience

В latency-sensitive системах:

• Resize вызывает spike от 10ms до 100+ms
• Решение: заранее рассчитать capacity
• Мониторинг: JFR jdk.HashMapResize event (Java 17+)

---

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

Обязательно знать:

• Новый массив = 2x от старого, элементы распределятся через битовый трюк (hash & oldCap)
• Lo List: остаются на месте, Hi List: перемещаются на index + oldCap
• Не пересчитывается hashCode — проверяется ОДИН бит
• Java 8+: Tail Insertion сохраняет порядок, предотвращает зацикливание (проблема Java 7)
• TreeNode.split(): при <= 6 элементов → untreeify (обратно в список)
• GC pressure: старый массив + новый = пиковое удвоение памяти массива

Частые уточняющие вопросы:

• Почему не пересчитывать хеш? — при удвоении степени двойки добавляется один бит в маску
• Что будет при конкурентном resize? — потеря элементов, undefined behavior
• Как ConcurrentHashMap делает resize? — параллельно, через transferIndex и ForwardingNode
• Сколько памяти при resize 1M → 2M? — ~32MB пик (два массива по ~16MB)

Красные флаги (НЕ говорить):

• «При resize пересчитываются все hashCode» — нет, проверяется один бит
• «HashMap потокобезопасна при resize» — нет, даже в Java 8+
• «Элементы случайно распределяются» — нет, детерминировано по одному биту

Связанные темы:

• [[17. Что такое capacity в HashMap]]
• [[18. Когда происходит rehashing в HashMap]]
• [[22. Как работает HashMap в многопоточной среде]]
• [[23. Что такое ConcurrentHashMap и чем он отличается от HashMap]]