Изменения

Перейти к: навигация, поиск

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

150 байт убрано, 08:16, 18 сентября 2017
При хеширования с открытой адресацией
При добавлении в хеш-таблицу большого количества элементов могут возникнуть ухудшения в ее работе. Обработка любого вызова будет занимать больше времени из-за увеличения размеров цепочек при открытом хешировании на списках или кластеризации при закрытомхешировании с открытой адресацией, также, при закрытом хешировании с открытой адресацией может произойти переполнение таблицы. Для избежания таких ситуаций используется выбор новой хеш-функции и (или) хеш-таблица большего размера. Этот процесс называется '''перехеширование'''(''rehashing'').  
==Перехеширование при разных типах хеширования==
===При открытом хешировании===
При использовании [[Открытое и закрытое хеширование#Открытое хеширование|открытого хеширования]] , элементы с одинаковым результатом хеш-функции помещают в список. Так как операции <tex>Add(x)</tex>, <tex>Exists(x)</tex> и <tex>Delete(x)</tex> работают за <tex>O(l)</tex>, где <tex>l</tex> - длина списка, то с некоторого момента выгодно увеличить размер хеш-таблицы, чтобы поддерживать амортизационную стоимость операции <tex>O(1)</tex>.
Рассмотрим следующий алгоритм перехеширования: когда в ===При хешировании цепочками=== При использовании [[Разрешение коллизий|хеширования цепочками]] , элементы с одинаковым результатом хеш-таблицу добавлено функции помещают в список. Так как операции <tex dpi = "150">\fracmathrm{4n}{3add(x)}</tex> элементов, где <tex>n\mathrm{contains(x)}</tex> - размер хеш-таблицы, создадим новую хеш-таблицу размера и <tex>2n\mathrm{remove(x)}</tex>, и последовательно переместим в нее все элементы первой таблицы. При этом, сменим хеш-функцию так, чтобы она выдавала значения работают за <tex>[0..2n-1]O(l)</tex> (в функциях, использующих остаток от деления на длину таблицы, достаточно брать остаток от деления на где <tex>2nl</tex> вместо остатка от деления на {{---}} длина списка, то с некоторого момента выгодно увеличить размер хеш-таблицы, чтобы поддерживать амортизационную стоимость операции <tex>nO(1)</tex>).
Найдем амортизационную стоимость добавления, после которого было сделано перехеширование, используя метод предоплаты. С момента последнего Рассмотрим следующий алгоритм перехеширования было произведено не менее : когда в хеш-таблицу добавлено <tex dpi = "150">\frac{2n4n}{3}</tex> операций элементов, где <tex>Add(x)n</tex>, так как изначально в массиве находится <tex dpi = "150">\frac{2n{---}{3}размер хеш-таблицы, создадим новую хеш-таблицу размера </tex> элементов (или <tex>02n</tex> , и последовательно переместим в начале работы)нее все элементы первой таблицы. При этом, сменим хеш-функцию так, а перехеширование происходит при наличии чтобы она выдавала значения <tex dpi = "150">\frac{4n}{3}[0..2n-1]</tex> элементов.
Для проведения Найдем амортизационную стоимость добавления, после которого было сделано перехеширование, используя метод предоплаты. С момента последнего перехеширования необходимо произвести было произведено не менее <tex dpi = "150">\frac{4n2n}{3}</tex> операций <tex>Add\mathrm{add(x)}</tex>, средняя стоимость которых составляет <tex>O(1)</tex> ''(Анализ открытого хеширования, см. Т.Корман, второе издание, стр. 288)'', потратить так как изначально в массиве находится <tex dpi = "150">\frac{4n2n}{3}</tex> операций на проход хеш-таблицыэлементов (или <tex>0</tex> в начале работы), и а перехеширование происходит при наличии <tex dpi = "150">\frac{4n}{3}</tex> операций на удаление предыдущей таблицы. В итоге, если мы увеличим стоимость каждой операции <tex>Add(x)</tex> на <tex>6</tex>, то есть на <tex>O(1)</tex>, операция перехеширования будет полностью предоплачена. Значит, амортизационная стоимость перехеширования при открытом типе хеш-таблицы равна <tex>O(1)</tex>элементов.
Для проведения перехеширования необходимо произвести <tex dpi ===При закрытом хешировании===При использовании хеширования с открытой адресацией, или [[Открытое и закрытое хеширование#Закрытое хеширование|закрытого хеширования]] , операции "150">\frac{4n}{3}</tex> операций <tex>Add\mathrm{add}(x)</tex>, средняя стоимость которых составляет <tex>ExistsO(x1)</tex> , потратить <tex dpi = "150">\frac{4n}{3}</tex> операций на проход хеш-таблицы, и <tex dpi = "150">\frac{4n}{3}</tex>Deleteопераций на удаление предыдущей таблицы. В итоге, если мы увеличим стоимость каждой операции <tex>\mathrm{add}(x)</tex> в худшем случае работают за на <tex>O(k)6</tex>, где то есть на <tex>kO(1)</tex> - количество уже добавленных в таблицу элементов, поэтому перехеширование надо проводить операция перехеширования будет полностью предоплачена. Значит, амортизационная стоимость перехеширования при неполном заполнении открытом типе хеш-таблицыравна <tex>O(1)</tex>.
Будем проводить перехеширование при заполнении таблицы на ===При хешировании с открытой адресацией===При использовании [[Разрешение коллизий|хеширования цепочками]] , операции <tex dpi = "150">\fracmathrm{nadd}{2}</tex>, увеличивая размер таблицы в <tex>2</tex> раза. Аналогично случаю с открытым хешированием, для перехеширования необходимо будет потратить <tex>O(nx)</tex> операций на обход таблицы, <tex>O(n)\cdot A</tex> элементарных операций на добавление элементов, где <tex>A</tex> - стоимость операции <tex>Addmathrm{contains}(x)</tex>, и <tex>O\mathrm{remove(nx)}</tex> операций на удаление таблицы. Так как <tex>A \geq 1</tex>, и между последовательными перехешированиями производится в худшем случае работают за <tex>O(nk)</tex> добавлений, то можно предоплатить перехеширование, увеличив стоимость операции где <tex>Add(x)</tex> на <tex>O(1)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>\mathrm{add(x)}</tex>, и <tex>O(n)</tex> операций на удаление таблицы. Так как <tex>A \geqslant 1</tex>, и между последовательными перехешированиями производится <tex>O(n)</tex> добавлений, то можно предоплатить перехеширование, увеличив стоимость операции <tex>\mathrm{add(x)}</tex> на <tex>O(1)</referencestex>, и не изменив стоимость остальных операций.
==См. также==
* [[Открытое и закрытое хеширование]]
==Источникиинформации==* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы«Алгоритмы: построение и анализ'''анализ», 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)* Дональд Кнут. «Искусство программирования, том 3. Сортировка и поиск» {{---}} «Вильямс», 2007 г.{{---}} ISBN 0-201-89685-0<references/> 
[[Категория: Дискретная математика и алгоритмы ]]
[[Категория: Амортизационный анализ]]
[[Категория: Хеширование]]
Анонимный участник

Навигация