Что такое load factor в HashMap

По умолчанию в HashMap значение коэффициента загрузки равно 0.75 (75%).

🟢 Junior Level

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

По умолчанию в 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");
    }
}

Аналогия: Представьте автобус с 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$

Разработчики Java (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$ вероятности длины цепочки в бакете составляют:

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 миллионов!)

Именно поэтому порог трификации (превращения в красно-чёрное дерево) был выбран равным 8: при стандартном loadFactor = 0.75 появление цепочки длиной 8 при нормальном хешировании практически невозможно. Если цепочка достигла 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: При первом вызове putVal срабатывает метод resize(). Он считывает oldThr, инициализирует массив Node<K,V>[] соответствующей степени двойки и пересчитывает настоящий порог:
```
newThr = (int)(newCap * loadFactor);
this.threshold = newThr;
```
Граничный случай MAXIMUM_CAPACITY: Если текущий 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 нс при попадании в кэш.
В микроархитектурных бенчмарках (JMH) доступ к HashMap с loadFactor = 0.5 на чтение может работать до 30–40% быстрее за счет более частого прямого попадания в заголовок бакета без перехода по ссылкам next.

4 Tricky Questions

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; и инициализируется исключительно в конструкторе. Возможности динамически изменить коэффициент загрузки в процессе работы нет (за исключением грязного взлома через Reflection/Unsafe).

Если бы это было разрешено, изменение коэффициента потребовало бы мгновенного пересчета 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);
// Либо формула: (int) (expectedSize / 0.75f + 1.0f)

Начиная с Java 19, в JDK добавлен специальный фабричный метод, инкапсулирующий этот расчет:

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

Внутри HashMap.newHashMap(numMappings) емкость вычисляется как (int) Math.ceil(numMappings / 0.75F).

4. Почему при уменьшении количества элементов (массовых `remove()`) `HashMap` не сжимается обратно, опираясь на `loadFactor`?

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

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

🎯 Шпаргалка для интервью

Суть Load Factor: Коэффициент загрузки (дефолт 0.75), задающий баланс «память vs скорость».
Формула порога: $\text{threshold} = \text{capacity} \times \text{loadFactor}$. Превышение size > threshold запускает resize().
Почему 0.75: Статистический оптимум (Пуассон). Средняя фактическая загрузка составляет $\approx 0.5$. Вероятность цепочки коллизий из 8 элементов составляет $\sim 6 \cdot 10^{-8}$.
Тюнинг:
- $0.5$ — для read-heavy и low-latency сценариев (минус: перерасход памяти под пустые бакеты).
- $0.85$–$0.95$ — для систем с жестким лимитом памяти (минус: рост коллизий и Cache Misses).
Создание под известный размер: Используйте HashMap.newHashMap(expectedSize) (Java 19+) или (int)(expected / 0.75f + 1).
Обратное сжатие: HashMap никогда не сжимает массив table при удалении элементов (remove()).

🟢 Junior Level

Как это работает

🟡 Middle Level

Баланс между памятью и временем поиска

Конструкторы с кастомным loadFactor

Влияние на итерацию по коллекции

🔴 Senior Level

Теоретическое обоснование: распределение Пуассона и среднее $\lambda \approx 0.5$

Внутреннее состояние и жизненный цикл threshold

Влияние на CPU Cache Locality

4 Tricky Questions

1. Можно ли передать loadFactor = 2.0f или loadFactor = Float.POSITIVE_INFINITY? Что произойдет?

2. Почему нельзя изменить loadFactor у уже созданного экземпляра HashMap?

3. Как правильно задать начальную емкость initialCapacity, чтобы при добавлении $N$ элементов гарантированно избежать хотя бы одного resize()?

4. Почему при уменьшении количества элементов (массовых remove()) HashMap не сжимается обратно, опираясь на loadFactor?