🔑 Розділ 10 · Питання #18

Коли відбувається rehashing в HashMap

У класі HashMap процедура resize() ініціюється в таких ключових ситуаціях:

🔑 HashMap equals hashCode 📄 Вихідний Markdown

🟢 Junior Level

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

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

У класі HashMap процедура resize() ініціюється в таких ключових ситуаціях:

  1. Перший виклик put() (лінива ініціалізація): При створенні new HashMap() масив бакетів не виділяється в оперативній пам’яті (table == null). Пам’ять під масив (за замовчуванням на 16 комірок) виділяється лише під час першого додавання даних.
  2. Перевищення порогу завантаження (threshold): Коли поточна кількість елементів size після чергової вставки перевищує значення capacity * loadFactor (за замовчуванням $16 \times 0.75 = 12$).
  3. Конфлікт колізій при малому розмірі таблиці: Якщо в одному бакеті накопичилося 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");
    }
}

[!NOTE] Аналогія: Рехешування схоже на переїзд офісу компанії в нову будівлю, вдвічі більшу за попередню. Переїзд відбувається або в перший робочий день (коли офіс фактично відкривається), або коли всі робочі місця зайняті більш ніж на 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:

  1. Алокація пам’яті: Створюється новий масив посилань подвоєного розміру ($O(N)$).
  2. Перенесення вузлів: Усі наявні елементи Node<K,V> скануються та перелінковуються в нові бакети ($O(N)$).
  3. Стрибок затримок (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

Глибокий аналіз коду тригерів у HotSpot JVM

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\) що дає константну вартість на один елемент.

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

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

Рехешування (resize) в HashMap запускається в 4 випадках: під час першого put() (лінива ініціалізація з 0 до 16), при перевищенні порогу ++size > threshold (після додавання чергового елемента), коли в бакеті накопичилося 8 елементів, але загальний capacity < 64 (ресайз замість побудови дерева) та превентивно у putAll(). Складність операції $O(N)$ за часом та пам’яттю. Завдяки геометричному подвоєнню ($2 \times$) досягається амортизована складність $O(1)$. Зворотного стиснення при видаленні не відбувається.

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

Питання 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 відсутній механізм автоматичного зменшення масиву бакетів. Масив table залишиться розміром понад 1 мільйон комірок (найближчий степінь двійки — $1\,048\,576$), займаючи близько 4–8 МБ пам’яті під порожні посилання. Якщо необхідно звільнити цю пам’ять, слід вручну створити новий екземпляр new HashMap<>(map) і віддати старий на збирання сміття (GC).

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

❌ «Ресайз відбувається перед кожною вставкою нового елемента.»
Правильно: У Java 8+ resize() викликається лише після перевищення threshold або під час першої вставки.

❌ «При досягненні 8 елементів у бакеті завжди створюється червоно-чорне дерево.»
Правильно: Якщо загальний розмір таблиці менший за 64 (table.length < 64), замість дерева викликається resize().

❌ «HashMap стискається у разі видалення більшості елементів.»
Правильно: Масив ніколи не зменшується назад.

4. Пов’язані питання