Що таке load factor в HashMap

За замовчуванням у класі HashMap значення коефіцієнта завантаження дорівнює 0.75 (тобто 75%).

🟢 Junior Level

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

Load Factor (коефіцієнт завантаження) — це числовий показник (дробове число типу float), що визначає ступінь заповненості геш-таблиці, при досягненні якого внутрішній масив бакетів автоматично подвоюється в розмірі (відбувається операція ресайзу resize()).

За замовчуванням у класі HashMap значення коефіцієнта завантаження дорівнює 0.75 (тобто 75%).

Як це працює

Під час створення HashMap виділяється масив бакетів початкової місткості (capacity, за замовчуванням 16). Поріг спрацьовування розширення (threshold) розраховується за формулою:

\[\text{threshold} = \text{capacity} \times \text{loadFactor} = 16 \times 0.75 = 12\]

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

public class LoadFactorDemo {
    public static void main(String[] args) {
        // Створюємо Map: capacity = 16, loadFactor = 0.75 -> threshold = 12
        Map<Integer, String> map = new HashMap<>();

        for (int i = 1; i <= 12; i++) {
            map.put(i, "Value " + i); // До 12 елементів включно ресайз не відбувається
        }

        // При додаванні 13-го елемента (size > threshold)
        // відбудеться resize: capacity стане 32, а threshold зросте до 24
        map.put(13, "Value 13");
    }
}

[!NOTE] Аналогія: Уявіть рейсовий автобус на 16 сидячих місць. Правило компанії-перевізника: щойно зайнято 75% місць (12 пасажирів), диспетчер викликає додатковий автобус (подвоює загальну місткість до 32), не чекаючи тисняви на вході, щоб нові пасажири заходили вільно і без затримок.

🟡 Middle Level

Баланс між пам’яттю та швидкістю пошуку

Значення loadFactor = 0.75 — це статистично вивірений компроміс між споживанням оперативної пам’яті та часовою складністю операцій get() і put():

Коефіцієнт завантаження	Витрати пам’яті	Ймовірність колізій	Швидкість пошуку / вставки
Низький (наприклад, 0.5)	Високі (половина бакетів порожні)	Мінімальна (бакети містять 0 або 1 елемент)	Максимальна (майже завжди чистий $O(1)$)
Стандартний (0.75)	Збалансовані	Низька (колізії трапляються рідко)	$O(1)$ у середньому
Високий (наприклад, 0.9–1.0)	Мінімальні (таблиця щільно упакована)	Висока (часті довгі ланцюжки)	Уповільнення (частіший обхід ланцюжків колізій)
Екстремальний (> 1.0)	Таблиця менша за кількість елементів	Невідворотні колізії	Деградація до лінійного пошуку за списком

Конструктори з кастомним `loadFactor`

Java надає можливість сконфігурувати коефіцієнт завантаження вручну:

Map<String, String> fastMap = new HashMap<>(64, 0.5f);
Map<String, String> compactMap = new HashMap<>(64, 0.9f);

Валідація параметрів: Значення loadFactor зобов’язане бути суворо додатним числом більшим за нуль (> 0) і не може бути Float.NaN. Інакше конструктор викине IllegalArgumentException:
```
if (loadFactor <= 0 || Float.isNaN(loadFactor))
    throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
```

Вплив на швидкість ітерації по колекції

Час ітерації по записах HashMap (keySet(), values(), entrySet()) пропорційний сумі поточної місткості таблиці та реальної кількості елементів: $\text{Time}(\text{Iteration}) \propto \text{capacity} + \text{size}$

Якщо встановити необґрунтовано низький loadFactor (наприклад, 0.1), місткість capacity роздується до гігантських розмірів при скромній кількості записів. У результаті ітератор буде змушений сканувати тисячі порожніх комірок null, що призведе до суттєвого уповільнення обходу.

🔴 Senior Level

Теоретичне обґрунтування: розподіл Пуассона та середнє $\lambda \approx 0.5$

Інженери OpenJDK навели детальне математичне обґрунтування вибору константи 0.75 безпосередньо у коментарях до сирцевого коду HashMap.java.

При якісному рівномірному розподілі геш-кодів кількість елементів у кожному конкретному бакеті підпорядковується розподілу Пуассона: $P(k) = \frac{e^{-\lambda} \lambda^k}{k!}$ де $k$ — кількість елементів в одному кошику, а $\lambda$ — середня довжина ланцюжка (математичне сподівання).

Хоча граничний поріг розширення дорівнює 0.75, одразу після операції ресайзу фактичний коефіцієнт завантаження падає вдвічі (до 0.375). Таким чином, середній коефіцієнт завантаження в часі становить близько 0.5 ($\lambda \approx 0.5$).

При $\lambda = 0.5$ теоретична ймовірність утворення ланцюжка довжиною $k$ становить:

0 елементів: $60.65\%$ ($e^{-0.5} \approx 0.6065$)
1 елемент: $30.33\%$
2 елементи: $7.58\%$
3 елементи: $1.26\%$
4 елементи: $0.16\%$
5 елементів: $0.016\%$
6 елементів: $0.0013\%$
7 елементів: $0.000094\%$
8 елементів: $\approx 0.00000006$ (лише 6 шансів на 100 мільйонів!)

Саме тому поріг перетворення ланцюжка на червоно-чорне дерево (treeification threshold) було обрано рівним 8: при стандартному loadFactor = 0.75 випадкова поява ланцюжка довжиною 8 при нормальному розподілі практично неможлива. Досягнення цієї межі майже завжди свідчить про патологічні колізії або спрямовану DoS-атаку Hash Flooding.

Внутрішній стан та життєвий цикл `threshold`

У коді HashMap поле loadFactor зафіксоване модифікатором final float loadFactor;.

Лінива ініціалізація: При виклику new HashMap(initialCapacity, loadFactor) масив table ще не виділяється в пам’яті купи! Поле threshold тимчасово використовується для збереження цільової початкової місткості, розрахованої через tableSizeFor(initialCapacity):
```
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
```
Перший put: При першому додаванні елемента викликається метод resize(). Він зчитує старий threshold, алокує масив Node<K,V>[] розміром найближчого степеня двійки і вперше обчислює справжній поріг:
```
newThr = (int)(newCap * loadFactor);
this.threshold = newThr;
```
Граничний випадок MAXIMUM_CAPACITY: Якщо поточна місткість досягає максимуму $2^{30}$ (1 << 30), значення threshold виставляється в Integer.MAX_VALUE ($2^{31} - 1$), і подальші спроби розширити таблицю блокуються.

Вплив на локальність кешу процесора (CPU Cache Locality)

При високому loadFactor (наприклад, 0.95 або 1.2):

Таблиця витрачає менше пам’яті на масив вказівників, але середня довжина зв’язних списків у бакетах зростає.
Обхід зв’язного списку Node змушує процесор стрибати по розрізнених ділянках оперативної пам’яті купи (Heap), спричиняючи промахи процесорного кешу (L1/L2/L3 Cache Misses). Затримка звернення до оперативної пам’яті (RAM) становить 60–100 нс проти 1–4 нс при читанні з кешу L1.
У мікроархітектурних тестах (JMH) читання з HashMap з loadFactor = 0.5 працює на 30–40% швидше завдяки прямому потраплянню в перший вузол бакета без переходу за вказівниками next.

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

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

Load Factor (типово 0.75) — це показник заповненості HashMap, при перевищенні якого внутрішній масив бакетів подвоюється. Поріг розширення розраховується як $\text{threshold} = \text{capacity} \times \text{loadFactor}$. Значення 0.75 є математично обґрунтованим компромісом (розподіл Пуассона): середня заповненість становить $\approx 0.5$, а ймовірність виникнення ланцюжка з 8 колізій не перевищує 1 до 16 мільйонів. Зменшення до $0.5$ прискорює пошук за рахунок пам’яті, а збільшення економить RAM, але деградує CPU Cache Locality.

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

Питання 1: Чи можна передати `loadFactor = 2.0f` або `loadFactor = Float.POSITIVE_INFINITY` і що відбудеться?

Відповідь:

loadFactor = 2.0f: Повністю валідно. Конструктор перевірить loadFactor > 0 і прийме значення. Таблиця розшириться лише тоді, коли кількість елементів перевищить $2 \times \text{capacity}$ (наприклад, при capacity = 16 ресайз відбудеться на 33-му елементі). У середньому в кожному бакеті буде по 2 елементи.
loadFactor = Float.POSITIVE_INFINITY: Конструктор не викине помилку, оскільки POSITIVE_INFINITY > 0 та !Float.isNaN(...). Проте при розрахунку newThr = (int)(newCap * loadFactor) виникне переповнення числа з плаваючою крапкою, і приведення до int поверне Integer.MAX_VALUE. Таблиця ніколи в житті не виконає resize() і назавжди залишиться початкового розміру, накопичуючи довгі ланцюжки колізій.

Питання 2: Чому не можна змінити `loadFactor` у вже створеного екземпляра `HashMap`?

Відповідь: Поле loadFactor задеклароване як final float loadFactor; і задається виключно в момент виклику конструктора. Можливості динамічно змінити його в процесі роботи немає. Якби це було дозволено, зміна коефіцієнта вимагала б негайного перерахунку threshold та потенційного термінового запуску важкої процедури рехешування прямо посеред обробки запиту. Єдиний коректний шлях — створити новий екземпляр new HashMap<>(newCap, newLoadFactor) і перенести дані через putAll().

Питання 3: Як правильно вказати початкову місткість `initialCapacity`, щоб при додаванні $N$ елементів гарантовано уникнути жодного `resize()`?

Відповідь: Типова помилка джуніорів — передати new HashMap<>(N): при $N=12$ capacity буде 16, threshold = 12, і вставка 13-го елемента викличе ресайз.
Щоб гарантовано вмістити $N$ елементів без розширення, місткість повинна задовольняти умову: $\text{capacity} \times \text{loadFactor} \ge N \implies \text{capacity} \ge \frac{N}{\text{loadFactor}}$ При стандартному loadFactor = 0.75f ділення на $0.75$ еквівалентне множенню на $\frac{4}{3}$:

int initialCapacity = (int) Math.ceil(expectedSize / 0.75f);

Починаючи з Java 19, у JDK додано фабричний метод, що інкапсулює цей розрахунок:

Map<Key, Value> map = HashMap.newHashMap(expectedSize);

Питання 4: Чому при масовому видаленні елементів (`remove()`) `HashMap` не стискає масив назад, спираючись на `loadFactor`?

Відповідь: HashMap принципово ніколи не зменшує розмір внутрішнього масиву table при операціях remove() чи clear() з двох причин:

Захист від флапінгу (Thrashing): Якби таблиця зменшувалася при зниженні завантаження нижче певного порогу, послідовність чергування put() і remove() на межі порогу спричиняла б безперервні цикли звуження та розширення масиву з повним рехешуванням, що фатально обвалило б продуктивність.
Передбачуваність пам’яті: Якщо застосунок одного разу зберіг $N$ елементів, із високою ймовірністю цей обсяг даних знадобиться знову в наступних бізнес-ітераціях.

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

❌ «Load Factor 0.75 означає, що 75% бакетів зайняті елементами.»
Правильно: Це коефіцієнт від загальної місткості до порогу розширення. Через колізії значна частина бакетів може бути порожньою, тоді як інші містять по кілька елементів.

❌ «Load factor можна динамічно змінити через сеттер.»
Правильно: Поле є final і фіксується в конструкторі назавжди.

❌ «Load Factor 1.0 є найефективнішим, оскільки немає порожніх бакетів.»
Правильно: При 1.0 суттєво зростає довжина ланцюжків колізій і частішають промахи процесорного кешу (Cache Misses).