106
правок
Изменения
Нет описания правки
===При хешировании цепочками===
При использовании [[Открытое и закрытое хеширование#Открытое хеширование|хеширования цепочками]] , элементы с одинаковым результатом хеш-функции помещают в список. Так как операции <tex>Add\mathrm{add(x)}</tex>, <tex>Contains(x)\mathrm{contains}</tex> и <tex>Remove\mathrm{remove(x)}</tex> работают за <tex>O(l)</tex>, где <tex>l</tex> {{---}} длина списка, то с некоторого момента выгодно увеличить размер хеш-таблицы, чтобы поддерживать амортизационную стоимость операции <tex>O(1)</tex>.
Рассмотрим следующий алгоритм перехеширования: когда в хеш-таблицу добавлено <tex dpi = "150">\frac{4n}{3}</tex> элементов, где <tex>n</tex> {{---}} размер хеш-таблицы, создадим новую хеш-таблицу размера <tex>2n</tex>, и последовательно переместим в нее все элементы первой таблицы. При этом, сменим хеш-функцию так, чтобы она выдавала значения <tex>[0..2n-1]</tex> (в функциях, использующих остаток от деления на длину таблицы, достаточно брать остаток от деления на <tex>2n</tex> вместо остатка от деления на <tex>n</tex>).
Найдем амортизационную стоимость добавления, после которого было сделано перехеширование, используя метод предоплаты. С момента последнего перехеширования было произведено не менее <tex dpi = "150">\frac{2n}{3}</tex> операций <tex>Add(x)</tex>, так как изначально в массиве находится <tex dpi = "150">\frac{2n}{3}</tex> элементов (или <tex>0</tex> в начале работы), а перехеширование происходит при наличии <tex dpi = "150">\frac{4n}{3}</tex> элементов.
Для проведения перехеширования необходимо произвести <tex dpi = "150">\frac{4n}{3}</tex> операций <tex>Add\mathrm{add}(x)</tex>, средняя стоимость которых составляет <tex>O(1)</tex> , потратить <tex dpi = "150">\frac{4n}{3}</tex> операций на проход хеш-таблицы, и <tex dpi = "150">\frac{4n}{3}</tex> операций на удаление предыдущей таблицы. В итоге, если мы увеличим стоимость каждой операции <tex>Add\mathrm{add}(x)</tex> на <tex>6</tex>, то есть на <tex>O(1)</tex>, операция перехеширования будет полностью предоплачена. Значит, амортизационная стоимость перехеширования при открытом типе хеш-таблицы равна <tex>O(1)</tex>.
===При хеширования с открытой адресацией===
При использовании [[Открытое и закрытое хеширование#Закрытое хеширование|хеширования с открытой адресацией]] , операции <tex>Add\mathrm{add}(x)</tex>, <tex>Contains\mathrm{contains}(x)</tex> и <tex>Remove\mathrm{remove(x)}</tex> в худшем случае работают за <tex>O(k)</tex>, где <tex>k</tex> {{---}} количество уже добавленных в таблицу элементов, поэтому перехеширование надо проводить при неполном заполнении хеш-таблицы.
Будем проводить перехеширование при заполнении таблицы на <tex dpi = "150">\frac{n}{2}</tex>, увеличивая размер таблицы в <tex>2</tex> раза. Аналогично случаю с открытым хешированием, для перехеширования необходимо будет потратить <tex>O(n)</tex> операций на обход таблицы, <tex>O(n)\cdot A</tex> элементарных операций на добавление элементов, где <tex>A</tex> {{---}} стоимость операции <tex>Add\mathrm{add(x)}</tex>, и <tex>O(n)</tex> операций на удаление таблицы. Так как <tex>A \geq 1</tex>, и между последовательными перехешированиями производится <tex>O(n)</tex> добавлений, то можно предоплатить перехеширование, увеличив стоимость операции <tex>Add\mathrm{add(x)}</tex> на <tex>O(1)</tex>, и не изменив стоимость остальных операций.
==См. также==
