Рехеширование¶

Рехеширование (от англ. rehashing; также перехеширование, повторное хеширование) — это процесс перестройки хеш-таблицы, при котором все существующие элементы перемещаются в новую, обычно большего размера, область памяти с пересчётом их хеш-кодов. Рехеширование применяется для поддержания эффективного времени доступа (в среднем O(1)) при росте числа хранимых записей, когда исходная таблица становится переполненной, что приводит к росту числа коллизий и снижению производительности.

¶Причины и цели

Основная причина рехеширования — увеличение нагрузки на хеш-таблицу. Коэффициент загрузки (load factor) — это отношение числа хранимых элементов к ёмкости таблицы. При превышении заданного порога (например, 0,75 для многих реализаций) количество коллизий при разрешении методом цепочек или открытой адресации резко возрастает, что ухудшает среднее время поиска, вставки и удаления с O(1) до O(n) в худшем случае.

Цели рехеширования:

• Уменьшение среднего числа коллизий.
• Восстановление амортизированной константной сложности операций.
• Оптимизация использования памяти (при необходимости уменьшения таблицы, когда много элементов удалено).

¶Алгоритм

Процесс рехеширования состоит из нескольких этапов:

1. Выбор новой ёмкости. Обычно размер таблицы увеличивается в 2–3 раза (или выбирается ближайшее простое число, чтобы уменьшить число коллизий). Для уменьшения таблицы размер может быть сокращён вдвое или до значения, при котором коэффициент загрузки становится ниже заданного минимума.
2. Выделение новой памяти. Создаётся новый массив корзин (buckets) или слотов нужного размера.
3. Перемещение элементов. Для каждого элемента из старой таблицы вычисляется его хеш-код (или используется уже сохранённый), затем определяется новый индекс в новой таблице (обычно по модулю новой ёмкости), и элемент вставляется в соответствующую корзину.
4. Освобождение старой памяти. После переноса всех элементов старый массив удаляется или помечается для сборки мусора (в языках с автоматическим управлением памятью).

¶Особенности реализации

• В некоторых реализациях (например, в HashMap в Java) рехеширование выполняется при каждом превышении порога загрузки. В других (например, в dict в Python) — по мере необходимости, с возможностью частичного рехеширования.
• Для хеш-таблиц с открытой адресацией (например, методом двойного хеширования) рехеширование может быть более сложным, так как требуется пересчёт всех проб.
• В системах с высокими требованиями к реальному времени (например, в ядрах операционных систем) применяется инкрементальное (постепенное) рехеширование, при котором элементы переносятся не за один раз, а порциями при каждой операции доступа, чтобы избежать длительных задержек.

¶Виды рехеширования

¶Полное рехеширование

Классический подход: вся таблица перестраивается за один проход. Преимущество — простота реализации. Недостаток — возможная задержка (latency spike) при выполнении операции, особенно если таблица содержит миллионы элементов.

¶Инкрементальное (постепенное) рехеширование

Используется в системах, где недопустимы длительные паузы (например, в базах данных, кэшах реального времени). При каждом обращении к таблице (поиск, вставка, удаление) переносится небольшое количество элементов (например, по одной корзине). Старая и новая таблицы сосуществуют до завершения переноса. Примеры: хеш-таблицы в ядре Linux (dcache), реализация ConcurrentHashMap в Java (начиная с версии 8).

¶Рехеширование с уменьшением

Применяется, когда из таблицы удалено много элементов и коэффициент загрузки стал слишком низким (например, ниже 0,25). Это позволяет экономить память. В некоторых реализациях (например, в std::unordered_map в C++) уменьшение может быть отключено по умолчанию.

¶Примеры в языках программирования

• Java: HashMap автоматически выполняет рехеширование при превышении коэффициента загрузки (по умолчанию 0,75). Ёмкость увеличивается в два раза. В ConcurrentHashMap используется инкрементальное рехеширование для поддержки многопоточности.
• Python: Словари (dict) используют рехеширование при заполнении на 2/3. Размер увеличивается в 2–4 раза (в зависимости от версии). В Python 3.6+ реализация была оптимизирована для уменьшения потребления памяти.
• C++: std::unordered_map рехешируется при превышении max_load_factor(). Вызов rehash(n) принудительно задаёт минимальное количество корзин.
• Go: Мапы (map) рехешируются автоматически, размер увеличивается примерно в 2 раза. При этом используется инкрементальный подход для снижения задержек.
• JavaScript (V8): Объекты и Map рехешируются по мере роста, но детали реализации скрыты и могут меняться между версиями движка.

¶Производительность и сложность

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

¶Факторы, влияющие на производительность:

• Качество хеш-функции (равномерность распределения).
• Порог коэффициента загрузки.
• Скорость выделения памяти.
• Размер переносимых элементов (особенно для больших объектов).

¶Критика и альтернативы

Рехеширование критикуется за:

• Задержки (latency spikes): полное рехеширование может вызвать паузу в миллисекунды или даже секунды для больших таблиц.
• Потребление памяти: в процессе рехеширования временно существуют две таблицы, что удваивает потребление памяти.
• Уязвимость к атакам: злоумышленник может подобрать данные, вызывающие частые коллизии и рехеширования, что приводит к отказу в обслуживании (DoS). Для защиты используются криптостойкие хеш-функции (например, SipHash) или рандомизация хеша.

Альтернативы рехешированию:

• Хеш-таблицы с фиксированным размером (например, для встраиваемых систем или кэшей с ограниченной памятью).
• Динамические хеш-таблицы на основе расширяемого хеширования (extendible hashing) или линейного хеширования (linear hashing), которые не требуют полного перестроения.
• Совершенное хеширование (perfect hashing) для статических наборов данных, где коллизии отсутствуют.

¶Источники

• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. «Алгоритмы: построение и анализ» (CLRS), 3-е издание, глава 11 «Хеш-таблицы».
• Седжвик Р., Уэйн К. «Алгоритмы на Java», 4-е издание, раздел 3.4 «Хеш-таблицы».
• Документация Oracle Java SE: класс java.util.HashMap.
• Документация Python: «Data Structures — Dictionaries».
• Статья «Rehashing» в Википедии (англ.).
• Статья «Incremental Rehashing in ConcurrentHashMap» — блог Oracle, 2014.