Изменения

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

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

Найдем амортизационную стоимость добавленияПри использовании [[Разрешение коллизий|хеширования цепочками]] , после которого было сделано перехеширование, используя метод предоплатыэлементы с одинаковым результатом хеш-функции помещают в список. С момента последнего перехеширования было произведено не менее Так как операции <tex>\fracmathrm{2}{3add(x)}n</tex> операций , <tex>Add\mathrm{contains(x)}</tex>, так как изначально в массиве находится и <tex>\fracmathrm{2remove(x)}{3}n</tex> элементов (или работают за <tex>0O(l)</tex> в начале работы), а перехеширование происходит при наличии где <tex>\fracl</tex> {{4---}{3}nдлина списка, то с некоторого момента выгодно увеличить размер хеш-таблицы, чтобы поддерживать амортизационную стоимость операции <tex>O(1)</tex> элементов.

Для проведения Рассмотрим следующий алгоритм перехеширования необходимо произвести : когда в хеш-таблицу добавлено <texdpi = "150">\frac{44n}{3}n</tex> операций <tex>Add(x)</tex>элементов, средняя стоимость которых составляет где <tex>O(1)n</tex> ''(Анализ открытого хеширования см. Т.Корман, второе издание, стр. 288)'', потратить <tex>\frac{4{---}{3}n</tex> операций на проход размер хеш-таблицы, и создадим новую хеш-таблицу размера <tex>\frac{4}{3}n2n</tex> операций на удаление предыдущей , и последовательно переместим в нее все элементы первой таблицы. В итогеПри этом, если мы увеличим стоимость каждой операции <tex>Add(x)</tex> на <tex>6</tex>сменим хеш-функцию так, то есть на чтобы она выдавала значения <tex>O(1)</tex>, операция перехеширования будет полностью предоплачена[0.. Значит, амортизационная стоимость перехеширования при открытом типе хеш2n-таблицы равна <tex>O(1)]</tex>.

===При закрытом типе===При использовании хеширования с открытой адресациейНайдем амортизационную стоимость добавления, после которого было сделано перехеширование, или закрытого хеширования[http://neercиспользуя метод предоплаты.ifmo.ru/mediawiki/index.php/%D0%9E%D1%82%D0%BA%D1%80%D1%8B%D1%82%D0%BE%D0%B5_%D0%B8_%D0%B7%D0%B0%D0%BA%D1%80%D1%8B%D1%82%D0%BE%D0%B5_%D1%85%D0%B5%D1%88%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5#.D0.97.D0.B0.D0.BA.D1.80.D1.8B.D1.82.D0.BE.D0.B5_.D1.85.D0.B5.D1.88.D0.B8.D1.80.D0.BE.D0.B2.D0.B0.D0.BD.D0.B8.D0.B5], операции С момента последнего перехеширования было произведено не менее <texdpi = "150">Add(x)\frac{2n}{3}</tex>, операций <tex>Exists\mathrm{add(x)}</tex> и , так как изначально в массиве находится <texdpi = "150">Delete(x)\frac{2n}{3}</tex> в худшем случае работают за элементов (или <tex>O(k)0</tex>в начале работы), где а перехеширование происходит при наличии <texdpi = "150">k\frac{4n}{3}</tex> - количество уже добавленных в таблицу элементов, поэтому перехеширование надо проводить при неполном заполнении хеш-таблицы.

Для проведения перехеширования необходимо произвести <tex dpi = "150">\frac{4n}{3}</tex> операций <tex>\mathrm{add}(x)</tex>, средняя стоимость которых составляет <tex>O(1)</tex> , потратить <tex dpi = "150">\frac{4n}{3}</tex> операций на проход хеш-таблицы, и <tex dpi = "150">\frac{4n}{3}</tex> операций на удаление предыдущей таблицы. В итоге, если мы увеличим стоимость каждой операции <tex>\mathrm{add}(x)</tex> на <tex>6</tex>, то есть на <tex>O(1)</tex>, операция перехеширования будет полностью предоплачена. Значит, амортизационная стоимость перехеширования при открытом типе хеш-таблицы равна <tex>O(1)</tex>. ===При хешировании с открытой адресацией===При использовании [[Разрешение коллизий|хеширования цепочками]] , операции <tex>\mathrm{add}(x)</tex>, <tex>\mathrm{contains}(x)</tex> и <tex>\mathrm{remove(x)}</tex> в худшем случае работают за <tex>O(k)</tex>, где <tex>k</tex> {{---}} количество уже добавленных в таблицу элементов, поэтому перехеширование надо проводить при неполном заполнении хеш-таблицы. Будем проводить перехеширование при заполнении таблицы на <texdpi = "150">\frac{1n}{2}n</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>Add\mathrm{add(x)}</tex> на <tex>O(1)</tex>, и не изменив стоимость остальных операций.

* [[Амортизационный анализ. Метод предоплаты]]

 ==Источникиинформации==* Т. ''Кормен, ЧТомас Х. , Лейзерсон, РЧарльз И. , Ривест: Алгоритмы, Рональд Л., Штайн Клиффорд'' «Алгоритмы: построение и анализанализ», 2-е издиздание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)* Дональд Кнут. «Искусство программирования, том 3. Сортировка и поиск» {{---}} «Вильямс», 2007 г.{{---}} ISBN 0-201-89685-0<references/>  [[Категория: Дискретная математика и алгоритмы ]][[Категория: Амортизационный анализ]][[Категория: Хеширование]]