🟢 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+ — экономия памяти,acceptable slowdown

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]]