1
правка
Изменения
→Линейное разрешение коллизий
'''Разрешение [[Хеш-таблица|коллизий]]''' (англ. collision resolution) в [[Хеш-таблица|хеш-таблице]], задача, решаемая несколькими способами: метод цепочек, открытая адресация и т.д. Можно использовать спискиОчень важно сводить количество коллизий к минимуму, а можно открытую адресациютак как это увеличивает время работы с хеш-таблицами.
Время работы поиска в наихудшем случае пропорционально длине списка, а если все <tex>n</tex> ключей захешировались в одну и ту же ячейку (создав список длиной <tex>n</tex>) время поиска будет равно <tex>\Theta(n)</tex> плюс время вычисления хеш-функции, что ничуть не лучше, чем использование связного списка для хранения всех <tex>n</tex> элементов. Удаления элемента может быть выполнено за <tex>O(1)</tex>, как и вставка, при использовании двухсвязного списка. == Линейное разрешение коллизий ==[[Файл:close_hash.png|thumb|380px|right|Пример хеш-таблицы с открытой адресацией и линейным пробированием.]]Все элементы хранятся непосредственно в хеш-таблице, без использования связных списков. В отличие от хеширования с цепочками, при использовании этого метода может возникнуть ситуация, когда хеш-таблица окажется полностью заполненной, следовательно, будет невозможно добавлять в неё новые элементы. Так что при возникновении такой ситуации решением может быть динамическое увеличение размера хеш-таблицы, с одновременной её перестройкой. === Стратегии поиска ===
''' Последовательный поиск '''
[[Файл:hashtables3.png|400px|Квадратичный поиск.]]
=== Проверка наличия элемента в таблице===
Проверка осуществляется аналогично добавлению: мы проверяем ячейку <tex>i</tex> и другие, в соответствии с выбранной стратегией, пока не найдём искомый элемент или свободную ячейку.
При поиске элемента может получится так, что мы дойдём до конца таблицы. Обычно поиск продолжается, начиная с другого конца, пока мы не придём в ту ячейку, откуда начинался поиск.
=== Проблемы данных стратегий ===
Проблем две — крайне нетривиальное удаление элемента из таблицы и образование кластеров — последовательностей занятых ячеек.
Кластеризация замедляет все операции с хеш-таблицей: при добавлении требуется перебирать всё больше элементов, при проверке тоже. Чем больше в таблице элементов, тем больше в ней кластеры и тем выше вероятность того, что добавляемый элемент попадёт в кластер.
Для защиты от кластеризации используется Двойное двойное хеширование и [[Хеширование кукушки|хеширование кукушки]].
=== Удаление элемента без пометок ===
Рассуждение будет описывать случай с линейным поиском хеша. Будем при удалении элемента сдвигать всё последующие на <tex>q</tex> позиций назад. При этом:
''' Псевдокод '''
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);
Хеш-таблицу считаем зацикленной
|statement=Асимптотически время работы <tex>\mathrm{delete}</tex> и <tex>\mathrm{find}</tex> совпадают
|proof=
Заметим что указатель <tex>j</tex> в каждой итерации перемещается вперёд на <tex>q</tex> (с учётом рекурсивных вызовов <tex>\mathrm{delete}</tex>). То есть этот алгоритм последовательно пройдёт по цепочке от удаляемого элемента до последнего {{- --}} с учётом вызова <tex>\mathrm{find}</tex> собственно для нахождения удаляемого элемента, мы посетим все ячейки цепи.
}}
==Двойное хеширование==
'''Двойное хеширование''' (англ. double hashing) {{---}} метод борьбы с коллизиями, возникающими при открытой адресации, основанный на использовании двух хеш-функций для построения различных последовательностей исследования хеш-таблицы.
===Принцип двойного хеширования===
===Простая реализация===
Пусть у нас есть некоторый объект <tex> item </tex>, в котором определено поле <tex> key </tex>, от которого можно вычислить хеш-функции <tex> \mathrm{h_1(key)}</tex> и <tex> \mathrm{h_2(key)} </tex>
Так же у нас есть таблица <tex> table </tex> величиной <tex> m </tex>, состоящая из объектов типа <tex> item </tex>.
'''Вставка'''
x = h1(item.key)
y = h2(item.key)
'''for''' (i = 0; i < ..m; i++) '''if''' table[x] == ''null''
table[x] = item
'''return'''
x = (x + y) '''mod ''' m table.resize() <span style="color:Green">//ошибка, требуется увеличить размер таблицы
'''Поиск'''
x = h1(key)
y = h2(key)
'''for''' (i = 0; i < ..m; i++) '''if''' table[x] != ''null''
'''if''' table[x].key == key
'''return''' table[x]
'''else'''
'''return''''' null'' x = (x + y) '''mod ''' m '''return''''' null''
===Реализация с удалением===
'''Вставка'''
x = h1(item.key)
y = h2(item.key)
'''for''' (i = 0; i < ..m; i++) '''if''' table[x] == '''null || ''' '''or''' deleted[x]
table[x] = item
deleted[x] = '''false'''
'''return'''
x = (x + i * y) '''mod ''' m table.resize() <span style="color:Green">//ошибка, требуется увеличить размер таблицы</pre>
'''Поиск'''
x = h1(key)
y = h2(key)
'''for''' (i = 0; i < ..m; i++) '''if''' table[x] != '''null''' '''if''' table[x].key == key && '''and''' !deleted[x]
'''return''' table[x]
'''else'''
'''return''' ''' null''' x = (x + y) '''mod ''' m '''return''' ''' null'''
'''Удаление'''
x = h1(key)
y = h2(key)
'''for''' (i = 0; i < ..m; i++) '''if''' table[x] != '''null'''
'''if''' table[x].key == key
deleted[x] = '''true'''
'''else'''
'''return'''
x = (x + y) '''mod ''' m
== Разрешение Альтернативная реализация метода цепочек==В 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 Разрешение коллизий]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Хеширование]]
[[Категория: Структуры данных]]
