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

Материал из Викиконспекты
Перейти к: навигация, поиск

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


Содержание

[править] Перехеширование при разных типах хеширования

[править] При хешировании цепочками

При использовании хеширования цепочками , элементы с одинаковым результатом хеш-функции помещают в список. Так как операции \mathrm{add(x)}, \mathrm{contains(x)} и \mathrm{remove(x)} работают за O(l), где l — длина списка, то с некоторого момента выгодно увеличить размер хеш-таблицы, чтобы поддерживать амортизационную стоимость операции O(1).

Рассмотрим следующий алгоритм перехеширования: когда в хеш-таблицу добавлено \frac{4n}{3} элементов, где n — размер хеш-таблицы, создадим новую хеш-таблицу размера 2n, и последовательно переместим в нее все элементы первой таблицы. При этом, сменим хеш-функцию так, чтобы она выдавала значения [0..2n-1].

Найдем амортизационную стоимость добавления, после которого было сделано перехеширование, используя метод предоплаты. С момента последнего перехеширования было произведено не менее \frac{2n}{3} операций \mathrm{add(x)}, так как изначально в массиве находится \frac{2n}{3} элементов (или 0 в начале работы), а перехеширование происходит при наличии \frac{4n}{3} элементов.

Для проведения перехеширования необходимо произвести \frac{4n}{3} операций \mathrm{add}(x), средняя стоимость которых составляет O(1) , потратить \frac{4n}{3} операций на проход хеш-таблицы, и \frac{4n}{3} операций на удаление предыдущей таблицы. В итоге, если мы увеличим стоимость каждой операции \mathrm{add}(x) на 6, то есть на O(1), операция перехеширования будет полностью предоплачена. Значит, амортизационная стоимость перехеширования при открытом типе хеш-таблицы равна O(1).

[править] При хеширования с открытой адресацией

При использовании хеширования цепочками , операции \mathrm{add}(x), \mathrm{contains}(x) и \mathrm{remove(x)} в худшем случае работают за O(k), где k — количество уже добавленных в таблицу элементов, поэтому перехеширование надо проводить при неполном заполнении хеш-таблицы.

Будем проводить перехеширование при заполнении таблицы на \frac{n}{2}, увеличивая размер таблицы в 2 раза. Аналогично случаю с открытым хешированием, для перехеширования необходимо будет потратить O(n) операций на обход таблицы, O(n)\cdot A элементарных операций на добавление элементов, где A — стоимость операции \mathrm{add(x)}, и O(n) операций на удаление таблицы. Так как A \geqslant 1, и между последовательными перехешированиями производится O(n) добавлений, то можно предоплатить перехеширование, увеличив стоимость операции \mathrm{add(x)} на O(1), и не изменив стоимость остальных операций.

[править] Источники

Личные инструменты
Пространства имён
Варианты
Действия
Навигация
Инструменты