Когда происходит Rehashing в HashMap?

Подробный ответ про Rehashing в HashMap

Rehashing (перехэширование) — это процесс увеличения внутреннего массива (table/buckets) HashMap и перераспределения всех существующих элементов в новые ячейки.

Когда происходит Rehashing?

Основное условие — превышение порогового значения загрузки:

// Псевдокод условия из исходников HashMap
if (size > threshold) {
    resize(); // Здесь и происходит rehashing
}

Конкретные триггеры:

1. Первоначальное заполнение при создании HashMap с элементами через Map.of() или putAll().
2. Добавление нового элемента (put(), putIfAbsent(), compute() и т.д.), которое увеличивает size сверх threshold.
3. Изменение capacity через ensureCapacity() может инициировать early rehashing.

Ключевые параметры, управляющие процессом

• Load Factor (коэффициент загрузки) — по умолчанию 0.75f. Определяет, насколько полно можно заполнить массив перед расширением.
• Threshold (порог) = capacity * loadFactor. Текущее максимальное количество элементов до расширения.
• Capacity (вместимость) — размер внутреннего массива, всегда степень двойки.

Пример процесса

// Создаем HashMap с начальной capacity = 16, load factor = 0.75
HashMap<String, Integer> map = new HashMap<>();

// Threshold = 16 * 0.75 = 12
// Первые 12 элементов помещаются без rehash
for (int i = 0; i < 12; i++) {
    map.put("key" + i, i); // Нет rehash
}

// 13-й элемент вызовет rehashing!
map.put("key12", 12); // size = 13 > threshold = 12 → происходит resize()

Что происходит во время Rehashing?

Последовательность действий:

1. Удвоение capacity (старая capacity * 2), максимум до MAXIMUM_CAPACITY = 1 << 30.
2. Пересчет threshold как newCapacity * loadFactor.
3. Создание нового массива с новой capacity.
4. Переиндексация всех элементов:
   • Для каждой entry вычисляется новый индекс: hash(key) & (newCapacity - 1)
   • В Java 8+ при коллизиях в bucket происходит преобразование из связанного списка в дерево или наоборот
5. Перенос данных в новый массив.

Важные нюансы

В Java 8+ оптимизации:

// В Java 8 появилась оптимизация для ускорения rehash
if ((e.hash & oldCapacity) == 0) {
    // Элемент остается в "нижней" половине
} else {
    // Элемент перемещается в "верхнюю" половину
}

Это работает потому что:

• Индекс = hash & (capacity - 1)
• При удвоении capacity, новый индекс = либо старый_индекс, либо старый_индекс + старая_capacity

Последствия и best practices

Проблемы:

• Временная блокировка — в однопоточных сценариях, в многопоточных без синхронизации — data corruption
• Производительность — O(n) операция, где n = количество элементов
• Порядок итерации может измениться (особенно актуально для LinkedHashMap)

Рекомендации:

// Если известно примерное количество элементов
int expectedSize = 1000;
float loadFactor = 0.75f;
int initialCapacity = (int) Math.ceil(expectedSize / loadFactor);
// 1000 / 0.75 ≈ 1333 → ближайшая степень двойки: 2048

HashMap<String, String> optimizedMap = new HashMap<>(initialCapacity, loadFactor);

Сравнительная таблица

Вывод

Rehashing — критически важный механизм, обеспечивающий амортизированную O(1) сложность операций в HashMap. Понимание его работы помогает:

1. Избегать частых rehash через правильную инициализацию
2. Оптимизировать использование памяти
3. Писать более эффективный код для работы с коллекциями

На практике в высоконагруженных приложениях рекомендуется всегда указывать начальную capacity при создании HashMap, если известно приблизительное количество элементов, чтобы минимизировать количество операций перехэширования.