Хэш-таблица: динамическое изменение размера

Когда вставка сделана так, что число записей в хэш-таблице превышает произведение коэффициента загрузки и текущей емкости, тогда хэш-таблицу необходимо будет перехэшировать. Перехэширование включает в себя увеличение размера базовой структуры данных и сопоставление существующих элементов с новыми местоположениями корзин. В некоторых реализациях, если начальная емкость больше, чем максимальное количество записей, деленное на коэффициент загрузки, операции перехэширования никогда не будут выполняться.

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

Изменение размера путем копирования всех записей

Обычный подход заключается в автоматическом запуске полного изменения размера, когда коэффициент загрузки превышает некоторый порог rmax. Затем выделяется новая большая таблица, каждая запись удаляется из старой таблицы и вставляется в новую таблицу. После удаления всех записей из старой таблицы старая таблица возвращается в пул свободных хранилищ. Аналогичным образом, когда коэффициент загрузки падает ниже второго порогового значения rmin, все записи перемещаются в новую меньшую таблицу.

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

Если размер таблицы увеличивается или уменьшается на фиксированный процент при каждом расширении, общая стоимость этих изменений, амортизированных по всем операциям вставки и удаления, остается постоянной, независимо от количества записей n и количества m выполненных операций.

Например, рассмотрим таблицу, которая была создана с минимально возможным размером и удваивается каждый раз, когда коэффициент загрузки превышает некоторый порог. Если в эту таблицу вставлено m элементов, общее количество дополнительных повторных вставок, которые происходят во всех динамических изменениях размера таблицы, составляет не более m - 1. Другими словами, динамическое изменение размеров примерно удваивает стоимость каждой операции вставки или удаления.

Альтернативы единовременному перехэшированию

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

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

Инкрементное изменение размера

Одной альтернативой одновременному увеличению таблицы является постепенное пошаговое перехэширование:

Во время изменения размера выделите новую хэш-таблицу, но оставьте старую таблицу без изменений.
В каждой операции поиска или удаления проверяйте обе таблицы.
Выполняйте операции вставки только в новой таблице.
При каждой вставке также перемещайте r элементов из старой таблицы в новую таблицу.
Когда все элементы будут удалены из старой таблицы, освободите (деаллоцируйте) ее.

Чтобы убедиться, что старая таблица полностью скопирована до того, как необходимо будет увеличить саму новую таблицу, необходимо увеличить размер таблицы как минимум (r + 1)/r во время изменения размера.

Монотонные ключи

Если известно, что значения ключей всегда будут монотонно увеличиваться (или уменьшаться), то можно добиться вариации согласованного хэширования, сохраняя список самых последних значений ключа в каждой операции изменения размера хэш-таблицы. При поиске ключи, попадающие в диапазоны, определенные этими записями списка, направляются в соответствующую хэш-функцию - и в действительности хэш-таблицу - обе из которых могут быть разными для каждого диапазона. Поскольку обычно удваивается общее количество записей путем удвоения, будут проверяться только диапазоны O(log(N)), а время двоичного поиска для перенаправления будет равно O(log(log(N))). Как и в случае последовательного хэширования, этот подход гарантирует, что хэш любого ключа после его выдачи никогда не изменится, даже если хэш-таблица будет позже увеличена.

Линейное хэширование

Линейное хэширование - это алгоритм хэш-таблицы, который допускает расширение инкрементной хэш-таблицы. Он реализован с использованием одной хэш-таблицы, но с двумя возможными функциями поиска.

Хэширование для распределенных хэш-таблиц

Еще один способ уменьшить стоимость изменения размера таблицы - это выбрать хэш-функцию таким образом, чтобы при изменении размера таблицы хэш-значения большинства значений не менялись. Такие хэш-функции широко распространены в дисковых и распределенных хэш-таблицах, где перехэширование обходится слишком дорого. Проблема создания хэш-функции, при которой большинство значений не изменяются при изменении размера таблицы, называется проблемой распределенной хэш-таблицы. Четырьмя наиболее популярными подходами являются хэширование рандеву, согласованное хэширование, сетевой алгоритм адресации контента и расстояние Kademlia.

Поиск по этому блогу

Alex tools