Изменения

{{Определение'''Разрешение [[Хеш-таблица|коллизий]]''' (англ. collision resolution) в [[Хеш-таблица|definition=Коллизия хеш-функции — таблице]], задача, решаемая несколькими способами: метод цепочек, открытая адресация и т.д. Очень важно сводить количество коллизий к минимуму, так как это равенство значений увеличивает время работы с хеш-таблицами.  == Разрешение коллизий с помощью цепочек ==[[Файл:open_hash.png|thumb|380px|right|Разрешение коллизий при помощи цепочек.]]Каждая ячейка <tex>i</tex> массива <tex>H</tex> содержит указатель на начало [[Список|списка]] всех элементов, хеш-функции код которых равен <tex>i</tex>, либо указывает на двух различных блоках данныхих отсутствие. Коллизии приводят к тому, что появляются списки размером больше одного элемента.}}

'''Разрешение коллизий''' в хеш-таблицеВ зависимости от того нужна ли нам уникальность значений операции вставки у нас будет работать за разное время. Если не важна, задачато мы используем список, решаемая несколькими способамивремя вставки в который будет в худшем случае равна <tex>O(1)</tex>. Можно использовать спискиИначе мы проверяем есть ли в списке данный элемент, а можно открытую адресациюпотом в случае его отсутствия мы его добавляем.В таком случае вставка элемента в худшем случае будет выполнена за <tex>O(n)</tex>

При использовании списков особых проблем не возникаетВремя работы поиска в наихудшем случае пропорционально длине списка, так как там а если все <tex>n</tex> ключей захешировались в каждой ячейке хранится одну и ту же ячейку (создав список длиной <tex>n</tex>) время поиска будет равно <tex>\Theta(n)</tex> плюс время вычисления хеш-функции, что ничуть не лучше, чем использование связного списка для хранения всех <tex>n</tex> элементов. При добавлении необходимо просто добавить элемент в начало списка.

При открытой адресации будет иначе: в каждой ячейке хеш-таблицы хранится только один элемент. Тогда при добавленииУдаления элемента может быть выполнено за <tex>O(1)</tex>, если ячейка свободна, мы просто записываем добавляемый элемент в эту ячейку. Однако если эта ячейка занята {{---}} необходимо поместить добавляемый элемент в какую-нибудь другую свободную ячейку. Такие ситуации нередки, так как невозможно использовать хеш-функциюи вставка, не дающую коллизий, а каждой ячейке таблицы соответствует одно значение хеш-функции. Далее мы рассмотрим несколько стратегий поиска свободного места в данном случаепри использовании двухсвязного списка.

== Линейное разрешение коллизий ==[[Файл:close_hash.png|thumb|380px|right|Пример хеш-таблицы с открытой адресацией и линейным пробированием.]]Все элементы хранятся непосредственно в хеш-таблице, без использования связных списков. В отличие от хеширования с цепочками, при использовании этого метода может возникнуть ситуация, когда хеш-таблица окажется полностью заполненной, следовательно, будет невозможно добавлять в неё новые элементы. Так что при возникновении такой ситуации решением может быть динамическое увеличение размера хеш-таблицы, с одновременной её перестройкой. === Стратегии поиска ===

=== Проверка наличия элемента в таблице===

=== Проблемы данных стратегий ===

Для защиты от кластеризации используется Двойное двойное хеширование и [[Хеширование кукушки|хеширование кукушки]].

 === Удаление элемента без пометок ===

'''function''' delete('''Item''' i) :

'''while ''' table[j] == ''null || '' '''or''' table[j].key != table[i].key '''if (''' table[j] == ''null)'' table[i] = ''null'' exit'''return'''

delete(j);

Заметим что указатель <tex>j</tex> в каждой итерации перемещается вперёд на <tex>q</tex> (с учётом рекурсивных вызовов <tex>\mathrm{delete}</tex>). То есть этот алгоритм последовательно пройдёт по цепочке от удаляемого элемента до последнего {{- --}} с учётом вызова <tex>\mathrm{find}</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> m </tex>, то в качестве <tex> h_2 </tex> можно использовать функцию вида <tex> h_2(k) = k \mod bmod (m-1) + 1 </tex>

<tex> h(k,i) = (h_1(k) + i \cdot h_2(k)) \mod bmod 13 </tex>

<tex> h_1(k) = k \mod bmod 13 </tex>

<tex> h_2(k) = 1 + k \mod bmod 11 </tex>

Мы хотим вставить ключ 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 свободна, значит записываем туда наш ключ.

<pre> '''function''' add('''Item''' item): 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">//ошибка, требуется увеличить размер таблицы</pre>

<pre> '''Item''' search('''Item''' key): 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</pre>''

Что бы Чтобы наша хеш-таблица поддерживала удаление, требуется добавить массив <tex>deleted</tex> типов <tex>bool</tex>, равный по величине массиву <tex>table</tex>. Теперь при удалении мы просто будем помечать наш объект ''как удалённый'', а при добавлении как ''не удалённый'' и замещать новым добавляемым объектом. При поиске, помимо равенства ключей, мы смотрим, удалён ли элемент, если да, то идём дальше.

<pre> '''function''' add('''Item''' item): 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 + y) '''mod ''' m table.resize() <span style="color:Green">//ошибка, требуется увеличить размер таблицы</pre> 

<pre> '''Item''' search('''Item''' key): 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</pre>'''

<pre> '''function''' remove('''Item''' key): 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</pre> == Разрешение коллизий с помощью списков == Каждая ячейка <tex>i</tex> массива <tex>H</tex> содержит указатель на начало списка всех элементов, хеш-код которых равен <tex>i</tex>, либо указывает на их отсутствие. Коллизии приводят к тому, что появляются списки размером больше одного элемента. Время, необходимое для вставки в наихудшем случае равно <tex>O(1)</tex>. Это операция выполняет быстро, так как считается, что вставляемый элемент отсутствует в таблице, но если потребуется, то перед вставкой мы можем выполнить поиск этого элемента.

==Альтернативная реализация метода цепочек==В Java 8 для разрешения коллизий используется модифицированный метод цепочек. Суть его заключается в том, что когда количество элементов в корзине превышает определенное значение, данная корзина переходит от использования связного списка к использованию [[Файл:open_hashАВЛ-дерево|сбалансированного дерева]].pngНо данный метод имеет смысл лишь тогда, когда на элементах хеш-таблицы задан [[Отношение порядка|420px|Разрешение коллизий линейный порядок]]. То есть при использовании данныx типа <tex>\mathbf{int}</tex> или <tex>\mathbf{double}</tex> имеет смысл переходить к дереву поиска, а при помощи цепочекиспользовании каких-нибудь ссылок на объекты не имеет, так как они не реализуют нужный интерфейс. Такой подход позволяет улучшить производительность с <tex>O(n)</tex> до <tex>O(\log(n))</tex>. Данный способ используется в таких коллекциях как HashMap, LinkedHashMap и ConcurrentHashMap.]]

Время работы поиска [[Файл:Hashing_in_Java8.png|500px|Хеширование в наихудшем случае пропорционально длине списка, а если все <tex>n</tex> ключей захешировались в одну и ту же ячейку (создав список длиной <tex>n</tex>) время поиска будет равно <tex>\Theta(n)</tex> плюс время вычисления хеш-функции, что ничуть не лучше, чем использование связного списка для хранения всех <tex>n</tex> элементов. Удаления элемента может быть выполнено за <tex>O(1)</tex>, как и вставка, при использовании двухсвязного спискаJava 8.]]

== Литература Источники информации ==* Бакнелл Дж. М. '''Фундаментальные «Фундаментальные алгоритмы и структуры данных в 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]