🟢 Junior Level

Load Factor (коефіцієнт завантаження) — це число, яке визначає, коли HashMap повинна збільшити свій розмір.

За замовчуванням load factor = 0.75 (75%).

Як це працює:

HashMap<String, Integer> map = new HashMap<>();
// capacity = 16, load factor = 0.75
// threshold = 16 * 0.75 = 12
// При додаванні 13-го елемента HashMap збільшиться до 32 бакетів

Проста аналогія: Уявіть стакан, наповнений водою на 75%. Якщо налити більше — вода переллється, і потрібно взяти стакан побільше. Load factor — це позначка “75%” на стакані.

Навіщо 0.75? Це баланс: не забагато порожніх місць (пам’ять) і не забагато колізій (швидкість).

🟡 Middle Level

Формула порогу розширення

threshold = capacity * loadFactor

Коли size > threshold, відбувається resize (подвоєння масиву).

Вплив на продуктивність та пам’ять

Load Factor	Пам’ять	Швидкість	Колізії
0.5 (низький)	Більше (50% порожніх бакетів)	Швидше (бакети містять 0-1 елемент, пошук майже завжди O(1) без обходу списків/дерев)	Мінімум колізій
0.75 (за замовчуванням)	Баланс	Баланс	Мало
0.9 (високий)	Менше	Повільніше	Більше
1.0+	Мінімум	Ще повільніше	Багато

Коли змінювати loadFactor?

Низький (0.5): Коли критична швидкість доступу (low latency системи)

new HashMap<>(1000, 0.5f); // Швидкий доступ, але 2x пам'ять

Високий (>0.75): Коли критична економія пам’яті (Embedded, IoT)

new HashMap<>(1000, 0.9f); // Економимо пам'ять, але більше колізій

Взаємодія з Initial Capacity

// Правильний розрахунок для 1000 елементів:
int capacity = (int)(1000 / 0.75f) + 1; // = 1334
Map<K, V> map = new HashMap<>(capacity, 0.75f);
// HashMap округлить до 2048, threshold = 1536

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

1. Load factor > 1.0 — допустимо, але пошук деградує до O(n)
2. Занадто низький — марна трата пам’яті, часті resize при малому заповненні
3. Не враховувати округлення — HashMap завжди округлює capacity до степеня двійки

🔴 Senior Level

Розподіл Пуассона

Вибір 0.75 обґрунтований статистично. При цьому коефіцієнті розподіл елементів по бакетах:

P(x) = (0.75^x * e^-0.75) / x!

x=0: 47.2%
x=1: 35.4%
x=2: 13.3%
x=8: 0.000006% — практично неможливо

Ймовірність ланцюжка з 8 елементів: 0.00000006. Treeification — захист від аномалій.

Cache Locality Impact

Високий load factor впливає на реальну продуктивність сильніше, ніж показує асимптотика:

• Довгі ланцюжки → вузли розкидані по Heap → Cache Miss
• Процесор чекає дані з RAM (100+ ns) замість L1/L2 cache (1-5 ns)
• O(log n) з поганою cache locality (вузли дерева розкидані по heap) може бути повільніше, ніж O(1) з хорошим load factor. CPU чекає дані з RAM (~100 ns) замість L1 cache (~1 ns).

Memory Footprint

При capacity = 1024:

• Load factor 0.5: 512 елементів, ~512 порожніх бакетів → ~4KB “втрат”
• Load factor 0.75: 768 елементів, ~256 порожніх → ~2KB “втрат”
• Load factor 0.9: 922 елементи, ~102 порожніх → ~1KB “втрат”

Edge Cases

1. Load factor = 1.0: Мінімум порожніх бакетів, але ланцюжки гарантовані
2. Load factor > 1.0: HashMap працює як масив списків, пошук O(n)
3. Load factor < 0.1: Екстремально швидкий, але 10x перевитрата пам’яті

Production Tuning

У високонавантажених системах:

• Read-heavy: load factor 0.5-0.6 — мінімум колізій, максимум швидкості
• Write-heavy: load factor 0.75 — баланс, менше resize
• Memory-constrained: load factor 0.9+ — економія пам’яті, прийнятне уповільнення

Monitoring

Для аналізу ефективності:

• Вимірюйте середню кількість елементів на бакет
• Порівнюйте latency get/put при різних load factors
• Використовуйте JFR для аналізу розподілу

---

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

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

• Load factor = 0.75 за замовчуванням — баланс між пам’яттю і колізіями
• threshold = capacity * loadFactor; при перевищенні — resize
• Розподіл Пуассона: при 0.75 ймовірність 8+ елементів у бакеті ≈ 0.00000006
• Низький LF (0.5): швидше, але 2x пам’ять; високий (0.9): економить пам’ять, але більше колізій
• Високий load factor = довгі ланцюжки = Cache Miss = реальна продуктивність гірша асимптотики
• LF > 1.0 допустимий, але пошук деградує до O(n)

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

• Коли використовувати LF = 0.5? — read-heavy, low latency системи
• Коли LF = 0.9? — memory-constrained (Embedded, IoT)
• Чому 0.75, а не 0.5 або 1.0? — статистично обґрунтований компроміс (Пуассон)
• Чи впливає LF на ітерацію? — опосередковано: більший capacity при низькому LF = повільніша ітерація

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

• «Load factor = 1.0 оптимальний» — ні, гарантовані ланцюжки і колізії
• «Можна змінювати load factor після створення» — ні, задається в конструкторі
• «0.75 означає 75% бакетів заповнені» — ні, 75% від capacity до resize

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

• [[17. Що таке capacity в HashMap]]
• [[18. Коли відбувається rehashing в HashMap]]
• [[28. Як правильно підібрати початкову capacity для HashMap]]