Изменения

{{Определение'''Разрешение [[Хеш-таблица|коллизий]]''' (англ. 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|Пример хеш-таблицы хранится только один элемент. Тогда при добавлении, если ячейка свободна, мы просто записываем добавляемый элемент в эту ячейкус открытой адресацией и линейным пробированием. Однако если эта ячейка занята {{---}} необходимо поместить добавляемый элемент ]]Все элементы хранятся непосредственно в какуюхеш-нибудь другую свободную ячейкутаблице, без использования связных списков. Такие ситуации нередкиВ отличие от хеширования с цепочками, при использовании этого метода может возникнуть ситуация, так как невозможно использовать когда хеш-функциютаблица окажется полностью заполненной, не дающую коллизийследовательно, а каждой ячейке таблицы соответствует одно значение будет невозможно добавлять в неё новые элементы. Так что при возникновении такой ситуации решением может быть динамическое увеличение размера хеш-функции. Далее мы рассмотрим несколько стратегий поиска свободного места в данном случаетаблицы, с одновременной её перестройкой.

=== Стратегии поиска ===

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

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

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

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

Рассуждение будет описывать случай с линейным поиском хеша. Будем при удалении элемента сдвигать всё последующие на шаг <tex>q</tex> позиций назад. При этом:

Учитывая это будем действовать следующим образом: при поиске следующего элемента цепочки будем пропускать все ячейки с другим значением хеша, первый найденный элемент копировать в текущую ячейку, и затем рекурсивно его удалять. Если такой следующей ячейки нет, то текущий элемент можно просто удалить, сторонние цепочки при этом не разрушатся (кстати это неверно для чего нельзя сказать про случай квадратичного поиска).

=== ''' Псевдокод ==='''  '''function''' delete('''Item''' i) :

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

delete(j);  Хеш-таблицу считаем зацикленной  {{Утверждение|about=о времени работы|statement=Асимптотически время работы <tex>\mathrm{delete}</tex> и <tex>\mathrm{find}</tex> совпадают|proof=Заметим что указатель <tex>j</tex> в каждой итерации перемещается вперёд на <tex>q</tex> (с учётом рекурсивных вызовов <tex>\mathrm{delete}</tex>). То есть этот алгоритм последовательно пройдёт по цепочке от удаляемого элемента до последнего {{---}} с учётом вызова <tex>\mathrm{find}</tex> собственно для нахождения удаляемого элемента, мы посетим все ячейки цепи.}}

Случай зацикливания Теперь докажем почему этот алгоритм работает. Собственно нам требуется сохранение трёх условий.* В редактируемой цепи не остаётся дырокДокажем по индукции. Если на данной итерации мы просто удаляем элемент (база), то после него ничего нет, всё верно. Если же нет, то вызванный в конце <tex>\mathrm{delete}</tex> (см. псевдокод) заметёт созданную дыру (скопированный элемент), и сам, по предположению, новых не создаст.* Элементы, которые уже на своих местах, не должны быть сдвинуты.Это учтено.* В других цепочках не рассматриваемпоявятся дырыПротивное возможно только в том случае, поскольку если q взаимнопросто с размером хешкакой-таблицыто элемент был действительно удалён. Удаляем мы только последнюю ячейку в цепи, то и если бы на её месте возникла дыра для зацикливания в ней вообще не должно быть свободных элементовсторонней цепочки, это бы означало что элемент, стоящий на <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> 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 + i * 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|Разрешение коллизий линейный порядок]]. То есть при использовании данный типа <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]