Что делает Load Factor?

# Load Factor в HashMap

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

Определение

Load Factor — это отношение количества элементов к размеру внутреннего массива (capacity):

Load Factor = количество элементов / размер массива

В Java HashMap имеет дефолтный load factor = 0.75

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

public class HashMap<K, V> {
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    int capacity = 16;
    int size = 0;
    
    public V put(K key, V value) {
        size++;
        if (size > capacity * loadFactor) {
            resize();
        }
        return null;
    }
}

Пример работы

Для HashMap с дефолтными параметрами:

• Начальная capacity = 16
• Load Factor = 0.75
• Порог (threshold) = 16 * 0.75 = 12

Элементы 1-12 добавляются в существующий массив, элемент 13 превышает порог и происходит RESIZE. Новая capacity = 32, новый порог = 24.

Процесс Resize

Когда load factor превышен, HashMap:

1. Создаёт новый массив большего размера (в 2 раза больше)
2. Пересчитывает хеши всех элементов
3. Перестраивает структуру данных (дорогая операция)

private void resize() {
    Node<K,V>[] oldTable = table;
    int oldCapacity = oldTable.length;
    int newCapacity = oldCapacity * 2;
    Node<K,V>[] newTable = new Node[newCapacity];
    
    for (Node<K,V> node : oldTable) {
        if (node != null) {
            int newIndex = hash(node.key) % newCapacity;
        }
    }
    
    this.table = newTable;
    this.threshold = newCapacity * loadFactor;
}

Влияние Load Factor на производительность

Высокий Load Factor (0.9+):

• Плюсы: экономится память, меньше resize операций
• Минусы: больше коллизий, медленнее поиск

Низкий Load Factor (0.25-):

• Плюсы: меньше коллизий, быстрый поиск
• Минусы: много пустого места, много resize операций

Дефолтное значение 0.75 — компромисс

Map<String, Integer> map1 = new HashMap<>();
Map<String, Integer> map2 = new HashMap<>(32, 0.5f);

Практические рекомендации

1. Используйте дефолтные значения (0.75) — оптимальный выбор
2. Если размер известен заранее, установите начальный размер явно
3. Избегайте частых resize операций — они дорогие
4. Мониторьте коллизии — если их много, увеличивайте capacity
5. При массовом добавлении элементов используйте конструктор HashMap(int initialCapacity, float loadFactor)