Что происходит при превышении load factor?

Расширение — это ключевой механизм поддержки производительности HashMap.

Определение

Resize — это процесс увеличения внутреннего массива бакетов и перераспределения всех элементов.

Когда происходит resize

Resize выполняется, когда:

• количество элементов превышает capacity * loadFactor

Например:

• capacity = 16

• loadFactor = 0.75

• threshold = 12

При добавлении 13-го элемента запускается расширение.

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

1. Создаётся новый массив (обычно в 2 раза больше)

2. Все элементы старой таблицы перебираются

3. Для каждого элемента пересчитывается бакет

4. Элементы размещаются в новом массиве

Почему это дорого

• Задействуется CPU

• Требуется дополнительная память

• Вставки временно замедляются

Почему это необходимо

Без resize:

• бакеты становились бы слишком длинными

• производительность деградировала бы до O(n)

Вывод

Resize — дорогая, но необходимая операция, поддерживающая стабильную производительность HashMap.