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

Question

При превышении load factor HashMap выполняет расширение (resize).Создаётся новый массив бакетов большего размера.Все существующие элементы перераспределяются по новым бакетам.Операция затратна по времени и памяти.После расширения количество коллизий уменьшается.

YeaHub · Accepted Answer

Расширение — это ключевой механизм поддержки производительности HashMap.ОпределениеResize — это процесс увеличения внутреннего массива бакетов и перераспределения всех элементов.Когда происходит resizeResize выполняется, когда:количество элементов превышает capacity * loadFactorНапример:capacity = 16loadFactor = 0.75threshold = 12При добавлении 13-го элемента запускается расширение.Что происходит во время resizeСоздаётся новый массив (обычно в 2 раза больше)Все элементы старой таблицы перебираютсяДля каждого элемента пересчитывается бакетЭлементы размещаются в новом массивеПочему это дорогоЗадействуется CPUТребуется дополнительная памятьВставки временно замедляютсяПочему это необходимоБез resize:бакеты становились бы слишком длиннымипроизводительность деградировала бы до O(n)ВыводResize — дорогая, но необходимая операция, поддерживающая стабильную производительность HashMap.