Что такое load factor и rehash в хеш-таблице?

Load factor — отношение числа элементов к числу ячеек; при превышении порога таблица увеличивается, и все ключи перераспределяются заново — это и есть rehash.

Зачем держать load factor низким

• При цепочках средняя длина списка ≈ load factor: поиск деградирует к O(n).
• При открытой адресации кластеры занятых ячеек растут ещё быстрее: типичный порог 0.5–0.7, для цепочек около 0.75.

Как происходит rehash

1. Выделяется массив примерно вдвое больше (степень двойки или простое число).
2. Каждый ключ перехешируется и кладётся в новую ячейку — разово это O(n).
3. Амортизированно вставка остаётся O(1): как в динамическом массиве, дорогая операция редка.

Нюансы

• Порядок итерации после rehash меняется — нельзя полагаться на него.
• Инкрементальный rehash переносит ячейки порциями между операциями, чтобы не было длинных пауз; так делают в системах реального времени и в Redis.

Коротко для собеседования

Чем выше load factor, тем длиннее цепочки и кластеры, поэтому при пороге около 0.75 таблицу увеличивают и раскладывают все ключи заново. Разовый rehash стоит O(n), но амортизированно вставка остаётся O(1); размер обычно берут степенью двойки, чтобы индекс считался битовой маской, а не делением.