🟢 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]]