1
правка
Изменения
→Линейное разрешение коллизий
Удаления элемента может быть выполнено за <tex>O(1)</tex>, как и вставка, при использовании двухсвязного списка. == Линейное разрешение коллизий ==[[Файл:close_hash.png|thumb|380px|right|Пример хеш-таблицы с открытой адресацией и линейным пробированием.]]Все элементы хранятся непосредственно в хеш-таблице, без использования связных списков. В отличие от хеширования с цепочками, при использовании этого метода может возникнуть ситуация, когда хеш-таблица окажется полностью заполненной, следовательно, будет невозможно добавлять в неё новые элементы. Так что при возникновении такой ситуации решением может быть динамическое увеличение размера хеш-таблицы, с одновременной её перестройкой. === Стратегии поиска ===
''' Последовательный поиск '''
[[Файл:hashtables3.png|400px|Квадратичный поиск.]]
=== Проверка наличия элемента в таблице===
Проверка осуществляется аналогично добавлению: мы проверяем ячейку <tex>i</tex> и другие, в соответствии с выбранной стратегией, пока не найдём искомый элемент или свободную ячейку.
При поиске элемента может получится так, что мы дойдём до конца таблицы. Обычно поиск продолжается, начиная с другого конца, пока мы не придём в ту ячейку, откуда начинался поиск.
=== Проблемы данных стратегий ===
Проблем две — крайне нетривиальное удаление элемента из таблицы и образование кластеров — последовательностей занятых ячеек.
Кластеризация замедляет все операции с хеш-таблицей: при добавлении требуется перебирать всё больше элементов, при проверке тоже. Чем больше в таблице элементов, тем больше в ней кластеры и тем выше вероятность того, что добавляемый элемент попадёт в кластер.
Для защиты от кластеризации используется Двойное двойное хеширование и [[Хеширование кукушки|хеширование кукушки]].
=== Удаление элемента без пометок ===
* если в цепочке встречается элемент с другим хешем, то он должен остаться на своём месте (такая ситуация может возникнуть если оставшаяся часть цепочки была добавлена позже этого элемента)
* в цепочке не должно оставаться "дырок", тогда любой элемент с данным хешем будет доступен из начала цепи
Учитывая это будем действовать следующим образом: при поиске следующего элемента цепочки будем пропускать все ячейки с другим значением хеша, копировать первый найденный элемент копировать в текущую ячейку , и затем рекурсивно его удалять. Если такой следующей ячейки нет, то текущий элемент можно просто удалить, сторонние цепочки при этом не разрушатся (кстати это неверно для чего нельзя сказать про случай квадратичного поиска). ''' Псевдокод ''' '''function''' delete('''Item''' i): j = i + q '''while''' table[j] == ''null'' '''or''' table[j].key != table[i].key '''if''' table[j] == ''null'' table[i] = ''null'' '''return''' j += q table[i] = table[j] delete(j)
Вариант с зацикливанием мы не рассматриваем, поскольку если <tex>q</tex> взаимнопросто с размером хеш-таблицы, то для зацикливания в ней вообще не должно быть свободных позиций
Теперь докажем почему этот алгоритм работает. Собственно нам требуется сохранение трёх условий.
* В редактируемой цепи не остаётся дырок
Докажем по индукции. Если на данной итерации мы просто удаляем элемент (база), то после него ничего нет, всё верно. Если же нет, то вызванный в конце <tex>\mathrm{delete}</tex> (см. псевдокод) заметёт созданную дыру (скопированный элемент), и сам, по предположению, новых не создаст.
* Элементы, которые уже на своих местах, не должны быть сдвинуты.
Это учтено.
* В других цепочках не появятся дыры
Противное возможно только в том случае, если какой-то элемент был действительно удалён. Удаляем мы только последнюю ячейку в цепи, и если бы на её месте возникла дыра для сторонней цепочки, это бы означало что элемент, стоящий на <tex>q</tex> позиций назад, одновременно принадлежал нашей и другой цепочкам, что невозможно.
==Двойное хеширование==
'''Двойное хеширование''' (англ. double hashing) {{---}} метод борьбы с коллизиями, возникающими при открытой адресации, основанный на использовании двух хеш-функций для построения различных последовательностей исследования хеш-таблицы.
===Принцип двойного хеширования===
При двойном хешировании используются две независимые хеш-функции <tex> h_1(k) </tex> и <tex> h_2(k) </tex>. Пусть <tex> k </tex> {{---}} это наш ключ, <tex> m </tex> {{---}} размер нашей таблицы, <tex>n \mod bmod m </tex> {{---}} остаток от деления <tex> n </tex> на <tex> m </tex>, тогда сначала исследуется ячейка с адресом <tex> h_1(k) </tex>, если она уже занята, то рассматривается <tex> (h_1(k) + h_2(k)) \mod bmod m </tex>, затем <tex> (h_1(k) + 2 \cdot h_2(k)) \mod bmod m </tex> и так далее. В общем случае идёт проверка последовательности ячеек <tex> (h_1(k) + i \cdot h_2(k)) \mod bmod m </tex> где <tex> i = (0, 1, \; ... \;, m - 1) </tex>
Таким образом, операции вставки, удаления и поиска в лучшем случае выполняются за <tex>O(1)</tex>, в худшем {{---}} за <tex>O(m)</tex>, что не отличается от обычного [[Открытое_и_закрытое_хеширование#Линейное разрешение коллизий|линейного разрешения коллизий]].
Есть два удобных способа это сделать. Первый состоит в том, что в качестве размера таблицы используется простое число, а <tex> h_2 </tex> возвращает натуральные числа, меньшие <tex> m </tex>. Второй {{---}} размер таблицы является степенью двойки, а <tex> h_2 </tex> возвращает нечетные значения.
Например, если размер таблицы равен <tex> m </tex>, то в качестве <tex> h_2 </tex> можно использовать функцию вида <tex> h_2(k) = k \mod bmod (m-1) + 1 </tex>
[[Файл: Вставка при двойном хэшировании.svg.jpeg|thumb|right|Вставка при двойном хешировании]]
<center>
<tex> h(k,i) = (h_1(k) + i \cdot h_2(k)) \mod bmod 13 </tex>
</center>
<center>
<tex> h_1(k) = k \mod bmod 13 </tex>
</center>
<center>
<tex> h_2(k) = 1 + k \mod bmod 11 </tex>
</center>
Мы хотим вставить ключ 14. Изначально <tex> i = 0 </tex>. Тогда <tex> h(14,0) = (h_1(14) + 0\cdot h_2(14)) \mod bmod 13 = 1 </tex>. Но ячейка с индексом 1 занята, поэтому увеличиваем <tex> i </tex> на 1 и пересчитываем значение хеш-функции. Делаем так, пока не дойдем до пустой ячейки. При <tex> i = 2 </tex> получаем <tex> h(14,2) = (h_1(14) + 2\cdot h_2(14)) \mod bmod 13 = 9 </tex>. Ячейка с номером 9 свободна, значит записываем туда наш ключ.
Таким образом, основная особенность двойного хеширования состоит в том, что при различных <tex> k </tex> пара <tex> (h_1(k),h_2(k)) </tex> дает различные последовательности ячеек для исследования.
'''Вставка'''
'''Поиск'''
===Реализация с удалением===
'''Вставка'''
'''Поиск'''
'''Удаление'''
== Разрешение Альтернативная реализация метода цепочек==В Java 8 для разрешения коллизий используется модифицированный метод цепочек. Суть его заключается в том, что когда количество элементов в корзине превышает определенное значение, данная корзина переходит от использования связного списка к использованию [[АВЛ-дерево|сбалансированного дерева]]. Но данный метод имеет смысл лишь тогда, когда на элементах хеш-таблицы задан [[Отношение порядка|линейный порядок]]. То есть при использовании данный типа <tex>\mathbf{int}</tex> или <tex>\mathbf{double}</tex> имеет смысл переходить к дереву поиска, а при использовании каких-нибудь ссылок на объекты не имеет, так как они не реализуют нужный интерфейс. Такой подход позволяет улучшить производительность с помощью списков ==<tex>O(n)</tex> до <tex>O(\log(n))</tex>. Данный способ используется в таких коллекциях как HashMap, LinkedHashMap и ConcurrentHashMap.
==См. также==
* [[Хеширование]]
* [[Хеширование_кукушки|Хеширование кукушки]]
* [[Идеальное_хеширование|Идеальное хеширование]]
== Литература Источники информации ==* Бакнелл Дж. М. '''Фундаментальные «Фундаментальные алгоритмы и структуры данных в Delphi'''Delphi», ''2003''* Кнут ДКормен, Томас Х. Э, Лейзерсон, Чарльз И. '''Искусство программирования, том 3Ривест, Рональд Л. Сортировка , Штайн Клиффорд «Алгоритмы: построение и поиск'''анализ», ''2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2000''2010.— Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)* Томас КорменДональд Кнут. «Искусство программирования, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайнтом 3. '''Алгоритмы. Построение Сортировка и анализ'''поиск» {{---}} «Вильямс», ''2010''2007 г.{{---}} ISBN 0-201-89685-0* Седжвик Р. '''Фундаментальные «Фундаментальные алгоритмы на C. Части 1-4. Анализ. Структуры данных. Сортировка. Поиск'''Поиск», ''2003'' ==Ссылки==* [http://openjdk.java.net/jeps/180 Handle Frequent HashMap Collisions with Balanced Trees]
* [http://en.wikipedia.org/wiki/Double_hashing Wikipedia {{---}} Double_hashing]
* [http://ru.wikipedia.org/wiki/%D0%A5%D0%B5%D1%88-%D1%82%D0%B0%D0%B1%D0%BB%D0%B8%D1%86%D0%B0 Разрешение коллизий]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Хеширование]]
[[Категория: Структуры данных]]