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

1️⃣ Как кратко ответить

Load factor в HashMap — это коэффициент, определяющий, насколько заполненной может быть хеш-таблица до её автоматического увеличения. По умолчанию равен 0.75, что означает, что при заполнении 75% емкости таблицы происходит её расширение для поддержания производительности.

2️⃣ Подробное объяснение темы

HashMap в Java — это структура данных, которая хранит элементы в виде пар "ключ-значение". Она использует хеширование для быстрого доступа к данным. Одним из ключевых параметров, влияющих на производительность HashMap, является load factor (коэффициент загрузки).

Что такое load factor?

Load factor — это дробное число, которое определяет, насколько заполненной может быть хеш-таблица, прежде чем произойдет её автоматическое увеличение. Он выражается в виде дроби, например, 0.75. Это означает, что когда хеш-таблица заполнена на 75%, она будет автоматически увеличена.

Зачем нужен load factor?

Load factor помогает сбалансировать компромисс между временем доступа и использованием памяти. Если load factor слишком низкий, то HashMap будет часто увеличиваться, что приведет к избыточному использованию памяти. Если он слишком высокий, то увеличится количество коллизий, что замедлит доступ к элементам.

Как работает load factor?

Когда количество элементов в HashMap превышает произведение текущей емкости и load factor, происходит увеличение емкости. Это называется "рехешированием". При этом создается новая, более крупная хеш-таблица, и все существующие элементы перехешируются и перемещаются в новую таблицу.

Пример кода:

import java.util.HashMap;
​
public class LoadFactorExample {
    public static void main(String[] args) {
        // Создаем HashMap с начальной емкостью 16 и load factor 0.75
        HashMap<Integer, String> map = new HashMap<>(16, 0.75f);
​
        // Добавляем элементы в HashMap
        for (int i = 0; i < 12; i++) {
            map.put(i, "Value" + i);
        }
​
        // Выводим размер и емкость HashMap
        System.out.println("Size: " + map.size()); // Текущий размер (количество элементов)
        System.out.println("Capacity: " + getCapacity(map)); // Текущая емкость (внутренний размер массива)
    }
​
    // Метод для получения текущей емкости HashMap (внутренний размер массива)
    private static int getCapacity(HashMap<?, ?> map) {
        try {
            // Доступ к приватному полю "table" через рефлексию
            java.lang.reflect.Field tableField = HashMap.class.getDeclaredField("table");
            tableField.setAccessible(true);
            Object[] table = (Object[]) tableField.get(map);
            return table == null ? 0 : table.length;
        } catch (Exception e) {
            throw new RuntimeException(e);
        }
    }
}

Комментарии к коду:

• HashMap<Integer, String> map = new HashMap<>(16, 0.75f);: Создаем HashMap с начальной емкостью 16 и load factor 0.75. Это означает, что при достижении 12 элементов (16 * 0.75) произойдет увеличение емкости.
• map.put(i, "Value" + i);: Добавляем элементы в HashMap. При добавлении 12-го элемента произойдет увеличение емкости.
• getCapacity(map): Используем рефлексию для получения текущей емкости внутреннего массива HashMap. Это демонстрационный метод, который показывает, как можно получить информацию о внутренней структуре HashMap.

Load factor — это важный параметр, который позволяет оптимизировать производительность HashMap, балансируя между временем доступа и использованием памяти.