🟢 Junior Level

Rehashing (resize) — це процес збільшення внутрішнього масиву HashMap. Він відбувається у трьох випадках:

1. Перший put() — при створенні HashMap масив порожній, перший put його створює
2. Перевищення порогу — коли кількість елементів > capacity * loadFactor
3. Treeification при малій таблиці — 8 елементів у бакеті і capacity < 64

Приклад:

HashMap<String, Integer> map = new HashMap<>(); // table = null
map.put("key1", 1);  // Перший put: створюється масив на 16 бакетів
// ... додаємо ще 11 елементів (всього 12)
map.put("key13", 13); // 13-й елемент: capacity збільшується до 32

Чому це важливо? Resize — повільна операція O(n). Краще заздалегідь задати потрібний розмір.

🟡 Middle Level

Тригери Resize

Тригер	Умова	Дія
Перший put	table == null	Створюється масив size 16
Перевищення порогу	++size > threshold	Подвоєння масиву
Treeification	8 елементів у бакеті, capacity < 64	Resize замість дерева

Формула порогу

threshold = capacity * loadFactor;
// За замовчуванням: 16 * 0.75 = 12

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

1. Створюється новий масив у 2 рази більший
2. Всі елементи переносяться в новий масив
3. Перераховується threshold

Продуктивність:

• Час: O(n) — проходить по всіх елементах
• Пам’ять: тимчасово існують два масиви
• GC pressure: створює навантаження на збирач сміття

Як уникнути resize?

// Якщо знаєте, що буде 1000 елементів:
int capacity = (int)(1000 / 0.75f) + 1;
new HashMap<>(capacity);

Типові помилки

1. Не враховувати округлення — new HashMap(1000) дасть capacity 1024, threshold 768
2. Ресайз в hot path — у циклі з частими put resize викликає latency spikes
3. Багатопотоковий resize — в Java 7 призводив до зациклення

Коли resize допустимий

Resize допустимий: при початковому завантаженні даних (одноразово), для некритичних за latency операцій. НЕ допустимий: в hot path обробника HTTP-запиту, в real-time системах.

🔴 Senior Level

Lazy Initialization

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length; // Перший resize!
    ...
}

Перший resize відбувається при першому put() — це створює початковий масив.

Resize при Treeification

Крім resize, при 8 елементах у бакеті і capacity < 64 відбувається resize ЗАМІСТЬ treeification — це спроба рознести елементи по нових бакетах, а не перетворювати список на дерево.

Multi-threaded Resize Danger

HashMap не потокобезпечна:

• Java 7: Паралельний resize → циклічні посилання → infinite loop
• Java 8+: Виправлено через tail insertion, але втрата даних можлива

// Потік A і B одночасно роблять resize:
// Обидва створюють новий масив, переносять елементи
// Результат: втрата елементів, undefined behavior

Performance Impact

Resize — одна з найдорожчих операцій HashMap:

• Алокація нового масиву: O(capacity)
• Копіювання елементів: O(size)
• Загальне: O(n)

У latency-sensitive системах це викликає spike від часток мілісекунди (для маленьких Map) до 100+ мс (для Map з мільйонами елементів; залежить від JVM і розміру HashMap).

Production Monitoring

Ознаки проблем з resize:

• Періодичні затримки (spikes) в метриках latency
• Зріст GC activity в моменти resize
• Memory profiling: одночасне існування двох масивів

Best Practices

// Guava:
Map<K, V> map = Maps.newHashMapWithExpectedSize(expectedSize);

// Або вручну:
new HashMap<>((int)(expectedSize / 0.75f) + 1);

---

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

Обов’язково знати:

• Три тригери: перший put (створення масиву), ++size > threshold, treeification при capacity < 64
• threshold = capacity * loadFactor; за замовчуванням 16 * 0.75 = 12
• Resize = O(n): алокація нового масиву + копіювання елементів
• Lazy Initialization: масив створюється при першому put, не в конструкторі (Java 8+)
• Java 7: паралельний resize → infinite loop; Java 8+: виправлено, але втрата даних можлива
• Resize в hot path — причина latency spikes

Часті уточнюючі запитання:

• Чому resize подвоює, а не +16? — подвоєння дає амортизовану O(1) вставку
• Чи можна уникнути resize? — так, задати initialCapacity = (expected / 0.75) + 1
• Чому treeification викликає resize? — спроба рознести елементи замість дерева
• Resize допустимий? — при початковому завантаженні так; в hot path HTTP-обробника — ні

Червоні прапорці (НЕ говорити):

• «Resize відбувається при кожному put» — ні, лише при перевищенні threshold
• «Java 8 повністю безпечна при resize» — ні, втрата даних все ще можлива
• «Resize перераховує hashCode» — ні, перевіряється один біт (hash & oldCap)

Пов’язані теми:

• [[16. Що таке load factor в HashMap]]
• [[17. Що таке capacity в HashMap]]
• [[19. Що відбувається під час rehashing]]
• [[22. Як HashMap працює в багатопотоковому середовищі]]