Що відбувається під час rehashing

4. Утилізація старого масиву: Внутрішнє посилання table перемикається на новий масив, а старий масив стає недосяжним для посилань і утилізується збирачем сміття (GC).

🟢 Junior Level

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

Rehashing (ресайз / перехешування) — це внутрішній процес HashMap, під час якого виділяється новий масив бакетів у 2 рази більшого розміру, а всі наявні елементи перерозподіляються по нових позиціях.

Що відбувається покроково:

Виділення нового масиву: Алокується новий масив Node<K,V>[] подвоєної місткості ($16 \to 32$, $32 \to 64$ тощо).
Перенесення елементів: Кожен елемент зі старого масиву переміщується в новий. При цьому кожен вузол або залишається на своєму попередньому індексі, або зміщується рівно на величину старий_індекс + стара_місткість.
Оновлення порогу (threshold): Поріг спрацьовування наступного ресайзу подвоюється.
Утилізація старого масиву: Внутрішнє посилання table перемикається на новий масив, а старий масив стає недосяжним для посилань і утилізується збирачем сміття (GC).

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

public class RehashingVisualDemo {
    public static void main(String[] args) {
        // Початкова місткість = 16, threshold = 12
        Map<Integer, String> map = new HashMap<>();

        for (int i = 1; i <= 12; i++) {
            map.put(i, "Value" + i);
        }

        // Вставка 13-го елемента запускає resize():
        // 1. Алокується новий масив на 32 комірки
        // 2. Усі 13 елементів переносяться за новими індексами
        // 3. Новий поріг стає рівним 24 (32 * 0.75)
        map.put(13, "TriggerResize");
    }
}

[!NOTE] Аналогія: Уявіть гардероб, у якому було 16 секцій із вішалками. Гардероб розширили до 32 секцій. Щоб не перевішувати кожну річ окремо, гардеробник розбирає кожну стару секцію за простим правилом: рівно половину речей залишає на тих самих номерах, а іншу половину переносить на 16 номерів уперед.

🟡 Middle Level

Елегантний бітовий трюк: `(e.hash & oldCap)`

Головне інженерне досягнення оптимізації resize() у Java 8+ полягає в тому, що HashMap узагалі не перераховує геш-коди і навіть не обчислює заново повний індекс операцією (newCap - 1) & hash.

Оскільки місткість таблиці завжди є степенем двійки ($2^k$), при її подвоєнні в бітовій масці з’являється рівно один новий старший біт (що відповідає вазі oldCap):

Стара місткість (16):   oldCap = 00010000_b
Стара маска (15):       n - 1  = 00001111_b
Нова місткість (32):    newCap = 00100000_b
Нова маска (31):        n - 1  = 00011111_b
                                 ^
                       Той самий новий біт!

Доля кожного елемента визначається значенням цього єдиного біта в збереженому полі e.hash:

if ((e.hash & oldCap) == 0) {
    // Новий біт дорівнює 0 -> індекс НЕ ЗМІНЮЄТЬСЯ (залишається oldIndex)
} else {
    // Новий біт дорівнює 1 -> індекс стає (oldIndex + oldCap)
}

Розділення ланцюжка: формування Lo- та Hi-списків

Під час обходу зв’язного списку бакета HashMap за один лінійний прохід формує два незалежні ланцюжки зі збереженням первинного порядку елементів (Tail Insertion):

Node<K,V> loHead = null, loTail = null; // Список для старого індексу
Node<K,V> hiHead = null, hiTail = null; // Список для нового індексу (index + oldCap)
Node<K,V> next;

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);

if (loTail != null) {
    loTail.next = null;
    newTab[j] = loHead; // Помістили в старий індекс
}
if (hiTail != null) {
    hiTail.next = null;
    newTab[j + oldCap] = hiHead; // Помістили в новий індекс зі зміщенням
}

Tail Insertion: Додавання нових елементів у хвіст списків гарантує збереження первинного порядку вузлів. У Java 7 використовувався Head Insertion (вставка в голову), через що при одночасному несинхронізованому доступі з кількох потоків ланцюжок розвертався у зворотний бік, утворюючи фатальне кільцеве зациклення посилань (Infinite Loop та 100% навантаження CPU).

🔴 Senior Level

Механізм `TreeNode.split()`: розщеплення червоно-чорного дерева

Якщо в бакеті вже побудовано червоно-чорне дерево (e instanceof TreeNode), виклик передається методу split(this, newTab, j, oldCap).

Вузол TreeNode має подвійну структуру: він одночасно є вузлом збалансованого дерева (left, right, parent) та елементом двозв’язного списку (prev, next).

Під час розділення дерева:

Метод split() проходить за зв’язками next двозв’язного списку, подібно до звичайного списку формуючи дві підгрупи: loHead та hiHead, одночасно підраховуючи їхні розміри (lc та hc).
Де-трифікація (Untreeification): Якщо кількість елементів в утвореній підгрупі $\le \text{UNTREEIFY_THRESHOLD}$ (6 елементів), дерево повертається назад у стан звичайного однозв’язного списку Node:
```
if (lc <= UNTREEIFY_THRESHOLD)
    tab[index] = loHead.untreeify(map);
else {
    tab[index] = loHead;
    if (hiHead != null)
        loHead.treeify(tab); // Повне ребалансування червоно-чорного дерева
}
```
Якщо ж у гілці залишилося 7 або більше елементів, заново викликається treeify(tab) для побудови збалансованого червоно-чорного дерева з перерахунком кольорів та обертань.

Навантаження на пам’ять та збирач сміття (GC Pressure)

Під час виконання методу resize():

Пікове споживання пам’яті: В оперативній пам’яті одночасно існують обидва масиви (oldTab та newTab).
При capacity = 2 мільйони: oldTab займає $\approx 8$ МБ посилань (при Compressed OOPs), а newTab на 4 мільйони — $\approx 16$ МБ. Сумарно короткочасно резервується 24 МБ під масиви посилань.
Write Barriers: Масове перезаписування посилань активує бар’єри запису (Write Barriers) сучасних GC (G1, ZGC), які фіксують зміни полів у Card Table та Remembered Sets.
Старий масив: Перетворюється на сміття одразу після завершення resize(). Якщо таблиця була довгоживучою і перебувала в Old Generation, звільнення пам’яті старого масиву вимагатиме циклу Concurrent Mark або Mixed GC у G1.

🎯 Шпаргалка для інтерв’ю

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

Під час ресайзу HashMap подвоює розмір масиву бакетів ($N \to 2N$) і переносить наявні елементи. У Java 8+ геші заново не обчислюються: доля вузла визначається значенням одного біта (e.hash & oldCap) == 0 — елемент або залишається на старій позиції, або переміщується на index + oldCap. Завдяки Tail Insertion порядок вузлів зберігається, що усунуло нескінченне зациклення з Java 7. Якщо бакет був деревом, метод split() ділить його на дві гілки: якщо у гілці лишається $\le 6$ вузлів, вона повертається у зв’язний список (untreeify).

2. 4 каверзні питання з глибокими відповідями

Питання 1: Чому при рехешуванні в Java 8+ метод `key.hashCode()` ніколи не викликається повторно?

Відповідь: У кожному вузлі Node<K,V> 32-бітний геш ключа обчислюється один-єдиний раз під час первинного додавання put() і кешується у незмінне поле final int hash;. Під час resize() HashMap просто зчитує готове поле e.hash і перевіряє один біт (e.hash & oldCap) == 0. Це повністю усуває витрати CPU на повторне гешування складних ключів (наприклад, довгих рядків або складених об’єктів).

Питання 2: Чому поріг де-трифікації (`UNTREEIFY_THRESHOLD = 6`) не дорівнює порогу трифікації (`TREEIFY_THRESHOLD = 8`)?

Відповідь: Різниця у 2 одиниці (поріг 8 для створення дерева і 6 для повернення до списку) — це класичний інженерний принцип гістерезису (захист від флапінгу / thrashing). Якби обидва пороги дорівнювали 8:

Додавання 8-го елемента створювало б дерево;
Видалення одного елемента (size = 7) відразу повертало б дерево до списку;
Наступний put() знову запускав би побудову дерева.
Постійна конвертація «список $\leftrightarrow$ дерево» під навантаженням призвела б до катастрофічного обвалу throughput. Зазор між 6 і 8 ефективно згладжує ці граничні коливання.

Питання 3: Що станеться, якщо потік А читає дані через `map.get("key")`, поки потік B виконує `resize()`?

Відповідь: HashMap не є потокобезпечною. У разі стану гонитви між читанням та ресайзом виникають такі аномалії:

Читання поверне null для реально наявного ключа: Метод resize() оновлює посилання table = newTab на початку процедури. Якщо потік A звернеться до нового масиву до того, як потік B перенесе туди потрібний бакет, потік A прочитає null і помилково вирішить, що запису в колекції немає.
ConcurrentModificationException під час ітерації: лічильник modCount не синхронізований, що призведе до збою ітератора.
Проблема видимості пам’яті: Відсутність модифікаторів volatile дозволяє ядрам CPU читати застарілі посилання next зі своїх внутрішніх кешів L1/L2.

Питання 4: Чи може місткість таблиці під час чергового ресайзу перевищити `MAXIMUM_CAPACITY` ($2^{30}$)?

Відповідь: Ні, місткість ніколи не перевищить $2^{30}$ ($1\,073\,741\,824$). У сирцевому коді resize() встановлено явний захисний бар’єр:

if (oldCap >= MAXIMUM_CAPACITY) {
    threshold = Integer.MAX_VALUE;
    return oldTab;
}

Якщо поточний capacity досяг $2^{30}$, HashMap припиняє розширювати масив і повертає oldTab. Поріг виставляється в Integer.MAX_VALUE ($2^{31} - 1$). Ресайз більше ніколи не запускатиметься, а всі наступні елементи розміщуватимуться в наявних бакетах, збільшуючи глибину дерев та списків.

3. Типові помилки та Red Flags

❌ «При ресайзі всі геш-коди ключів перераховуються заново.»
Правильно: Значення e.hash кешується у вузлі і не перераховується. Перевіряється лише один біт (e.hash & oldCap) == 0.

❌ «Дерево розпадається на список, якщо в ньому стало менше 8 елементів.»
Правильно: Поріг де-трифікації становить $\le 6$ елементів (гістерезис).

❌ «HashMap у Java 8+ повністю безпечна для багатопотокового ресайзу.»
Правильно: Tail Insertion ліквідував циклічне зависання JVM, але гонки даних, втрата елементів та фантомні null при читанні все ще неминучі.