http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&user=93.92.207.162&feedformat=atomВикиконспекты - Вклад участника [ru]2024-03-28T16:51:59ZВклад участникаMediaWiki 1.30.0http://neerc.ifmo.ru/wiki/index.php?title=%D0%A0%D0%B0%D0%B7%D1%80%D0%B5%D1%88%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BA%D0%BE%D0%BB%D0%BB%D0%B8%D0%B7%D0%B8%D0%B9&diff=65937Разрешение коллизий2018-06-11T10:27:36Z<p>93.92.207.162: grammar</p>
<hr />
<div>'''Разрешение [[Хеш-таблица|коллизий]]''' (англ. collision resolution) в [[Хеш-таблица|хеш-таблице]], задача, решаемая несколькими способами: метод цепочек, открытая адресация и т.д. Очень важно сводить количество коллизий к минимуму, так как это увеличивает время работы с хеш-таблицами. <br />
<br />
== Разрешение коллизий с помощью цепочек ==<br />
[[Файл:open_hash.png|thumb|380px|right|Разрешение коллизий при помощи цепочек.]]<br />
Каждая ячейка <tex>i</tex> массива <tex>H</tex> содержит указатель на начало [[Список|списка]] всех элементов, хеш-код которых равен <tex>i</tex>, либо указывает на их отсутствие. Коллизии приводят к тому, что появляются списки размером больше одного элемента.<br />
<br />
В зависимости от того нужна ли нам уникальность значений операции вставки у нас будет работать за разное время. Если не важна, то мы используем список, время вставки в который будет в худшем случае равна <tex>O(1)</tex>. Иначе мы проверяем есть ли в списке данный элемент, а потом в случае его отсутствия мы его добавляем. В таком случае вставка элемента в худшем случае будет выполнена за <tex>O(n)</tex><br />
<br />
Время работы поиска в наихудшем случае пропорционально длине списка, а если все <tex>n</tex> ключей захешировались в одну и ту же ячейку (создав список длиной <tex>n</tex>) время поиска будет равно <tex>\Theta(n)</tex> плюс время вычисления хеш-функции, что ничуть не лучше, чем использование связного списка для хранения всех <tex>n</tex> элементов.<br />
<br />
Удаления элемента может быть выполнено за <tex>O(1)</tex>, как и вставка, при использовании двухсвязного списка.<br />
<br />
== Линейное разрешение коллизий ==<br />
[[Файл:close_hash.png|thumb|380px|right|Пример хеш-таблицы с открытой адресацией и линейным пробированием.]]<br />
Все элементы хранятся непосредственно в хеш-таблице, без использования связных списков. В отличие от хеширования с цепочками, при использовании этого метода может возникнуть ситуация, когда хеш-таблица окажется полностью заполненной, следовательно будет невозможно добавлять в неё новые элементы. Так что при возникновении такой ситуации решением может быть динамическое увеличение размера хеш-таблицы, с одновременной её перестройкой.<br />
<br />
=== Стратегии поиска ===<br />
<br />
''' Последовательный поиск '''<br />
<br />
При попытке добавить элемент в занятую ячейку <tex>i</tex> начинаем последовательно просматривать ячейки <tex>i+1, i+2, i+3</tex> и так далее, пока не найдём свободную ячейку. В неё и запишем элемент.<br />
<br />
[[Файл:hashtables1.png|400px|Последовательный поиск, частный случай линейного поиска.]]<br />
<br />
''' Линейный поиск '''<br />
<br />
Выбираем шаг <tex>q</tex>. При попытке добавить элемент в занятую ячейку <tex>i</tex> начинаем последовательно просматривать ячейки <tex>i+(1 \cdot q), i+(2 \cdot q), i+(3 \cdot q)</tex> и так далее, пока не найдём свободную ячейку. В неё и запишем элемент.<br />
По сути последовательный поиск - частный случай линейного, где <tex>q=1</tex>.<br />
<br />
[[Файл:Hashtables56.PNG|400px|Линейный поиск с шагом q.]]<br />
<br />
''' Квадратичный поиск '''<br />
<br />
Шаг <tex>q</tex> не фиксирован, а изменяется квадратично: <tex>q = 1,4,9,16...</tex>. Соответственно при попытке добавить элемент в занятую ячейку <tex>i</tex> начинаем последовательно просматривать ячейки <tex> i+1, i+4, i+9</tex> и так далее, пока не найдём свободную ячейку.<br />
<br />
[[Файл:hashtables3.png|400px|Квадратичный поиск.]]<br />
<br />
=== Проверка наличия элемента в таблице===<br />
<br />
Проверка осуществляется аналогично добавлению: мы проверяем ячейку <tex>i</tex> и другие, в соответствии с выбранной стратегией, пока не найдём искомый элемент или свободную ячейку.<br />
<br />
При поиске элемента может получится так, что мы дойдём до конца таблицы. Обычно поиск продолжается, начиная с другого конца, пока мы не придём в ту ячейку, откуда начинался поиск.<br />
<br />
=== Проблемы данных стратегий ===<br />
<br />
Проблем две — крайне нетривиальное удаление элемента из таблицы и образование кластеров — последовательностей занятых ячеек.<br />
<br />
Кластеризация замедляет все операции с хеш-таблицей: при добавлении требуется перебирать всё больше элементов, при проверке тоже. Чем больше в таблице элементов, тем больше в ней кластеры и тем выше вероятность того, что добавляемый элемент попадёт в кластер.<br />
Для защиты от кластеризации используется двойное хеширование и [[Хеширование кукушки|хеширование кукушки]].<br />
<br />
=== Удаление элемента без пометок ===<br />
<br />
Рассуждение будет описывать случай с линейным поиском хеша. Будем при удалении элемента сдвигать всё последующие на <tex>q</tex> позиций назад. При этом:<br />
* если в цепочке встречается элемент с другим хешем, то он должен остаться на своём месте (такая ситуация может возникнуть если оставшаяся часть цепочки была добавлена позже этого элемента)<br />
* в цепочке не должно оставаться "дырок", тогда любой элемент с данным хешем будет доступен из начала цепи<br />
<br />
Учитывая это будем действовать следующим образом: при поиске следующего элемента цепочки будем пропускать все ячейки с другим значением хеша, первый найденный элемент копировать в текущую ячейку, и затем рекурсивно его удалять. Если такой следующей ячейки нет, то текущий элемент можно просто удалить, сторонние цепочки при этом не разрушатся (чего нельзя сказать про случай квадратичного поиска).<br />
<br />
<br />
''' Псевдокод '''<br />
<br />
'''function''' delete('''Item''' i):<br />
j = i + q<br />
'''while''' table[j] == ''null'' '''or''' table[j].key != table[i].key<br />
'''if''' table[j] == ''null''<br />
table[i] = ''null''<br />
'''return'''<br />
j += q<br />
table[i] = table[j]<br />
delete(j) <br />
<br />
Хеш-таблицу считаем зацикленной<br />
<br />
<br />
{{Утверждение<br />
|about=о времени работы<br />
|statement=Асимптотически время работы <tex>\mathrm{delete}</tex> и <tex>\mathrm{find}</tex> совпадают<br />
|proof=<br />
Заметим что указатель <tex>j</tex> в каждой итерации перемещается вперёд на <tex>q</tex> (с учётом рекурсивных вызовов <tex>\mathrm{delete}</tex>). То есть этот алгоритм последовательно пройдёт по цепочке от удаляемого элемента до последнего {{---}} с учётом вызова <tex>\mathrm{find}</tex> собственно для нахождения удаляемого элемента, мы посетим все ячейки цепи.<br />
}}<br />
<br />
Вариант с зацикливанием мы не рассматриваем, поскольку если <tex>q</tex> взаимнопросто с размером хеш-таблицы, то для зацикливания в ней вообще не должно быть свободных позиций<br />
<br />
<br />
Теперь докажем почему этот алгоритм работает. Собственно нам требуется сохранение трёх условий.<br />
* В редактируемой цепи не остаётся дырок<br />
Докажем по индукции. Если на данной итерации мы просто удаляем элемент (база), то после него ничего нет, всё верно. Если же нет, то вызванный в конце <tex>\mathrm{delete}</tex> (см. псевдокод) заметёт созданную дыру (скопированный элемент), и сам, по предположению, новых не создаст.<br />
* Элементы, которые уже на своих местах, не должны быть сдвинуты.<br />
Это учтено.<br />
* В других цепочках не появятся дыры<br />
Противное возможно только в том случае, если какой-то элемент был действительно удалён. Удаляем мы только последнюю ячейку в цепи, и если бы на её месте возникла дыра для сторонней цепочки, это бы означало что элемент, стоящий на <tex>q</tex> позиций назад, одновременно принадлежал нашей и другой цепочкам, что невозможно.<br />
<br />
==Двойное хеширование==<br />
'''Двойное хеширование''' (англ. double hashing) {{---}} метод борьбы с коллизиями, возникающими при открытой адресации, основанный на использовании двух хеш-функций для построения различных последовательностей исследования хеш-таблицы.<br />
<br />
===Принцип двойного хеширования===<br />
При двойном хешировании используются две независимые хеш-функции <tex> h_1(k) </tex> и <tex> h_2(k) </tex>. Пусть <tex> k </tex> {{---}} это наш ключ, <tex> m </tex> {{---}} размер нашей таблицы, <tex>n \bmod m </tex> {{---}} остаток от деления <tex> n </tex> на <tex> m </tex>, тогда сначала исследуется ячейка с адресом <tex> h_1(k) </tex>, если она уже занята, то рассматривается <tex> (h_1(k) + h_2(k)) \bmod m </tex>, затем <tex> (h_1(k) + 2 \cdot h_2(k)) \bmod m </tex> и так далее. В общем случае идёт проверка последовательности ячеек <tex> (h_1(k) + i \cdot h_2(k)) \bmod m </tex> где <tex> i = (0, 1, \; ... \;, m - 1) </tex><br />
<br />
Таким образом, операции вставки, удаления и поиска в лучшем случае выполняются за <tex>O(1)</tex>, в худшем {{---}} за <tex>O(m)</tex>, что не отличается от обычного [[Открытое_и_закрытое_хеширование#Линейное разрешение коллизий|линейного разрешения коллизий]].<br />
Однако в среднем, при грамотном выборе хеш-функций, двойное хеширование будет выдавать лучшие результаты, за счёт того, что вероятность совпадения значений сразу двух независимых хеш-функций ниже, чем одной.<br />
<br />
<center><br />
<tex>\forall x \neq y \; \exists h_1,h_2 : p(h_1(x)=h_1(y))> p((h_1(x)=h_1(y)) \land (h_2(x)=h_2(y)))</tex><br />
</center><br />
<br />
===Выбор хеш-функций===<br />
<tex> h_1 </tex> может быть обычной хеш-функцией. Однако чтобы последовательность исследования могла охватить всю таблицу, <tex> h_2 </tex> должна возвращать значения:<br />
*не равные <tex> 0 </tex><br />
*независимые от <tex> h_1 </tex><br />
*взаимно простые с величиной хеш-таблицы<br />
<br />
Есть два удобных способа это сделать. Первый состоит в том, что в качестве размера таблицы используется простое число, а <tex> h_2 </tex> возвращает натуральные числа, меньшие <tex> m </tex>. Второй {{---}} размер таблицы является степенью двойки, а <tex> h_2 </tex> возвращает нечетные значения.<br />
<br />
Например, если размер таблицы равен <tex> m </tex>, то в качестве <tex> h_2 </tex> можно использовать функцию вида <tex> h_2(k) = k \bmod (m-1) + 1 </tex><br />
<br />
[[Файл: Вставка при двойном хэшировании.svg.jpeg|thumb|right|Вставка при двойном хешировании]]<br />
<br />
===Пример===<br />
<br />
Показана хеш-таблица размером 13 ячеек, в которой используются вспомогательные функции:<br />
<br />
<center><br />
<tex> h(k,i) = (h_1(k) + i \cdot h_2(k)) \bmod 13 </tex><br />
</center><br />
<br />
<center><br />
<tex> h_1(k) = k \bmod 13 </tex><br />
</center><br />
<br />
<center><br />
<tex> h_2(k) = 1 + k \bmod 11 </tex><br />
</center><br />
<br />
Мы хотим вставить ключ 14. Изначально <tex> i = 0 </tex>. Тогда <tex> h(14,0) = (h_1(14) + 0\cdot h_2(14)) \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)) \bmod 13 = 9 </tex>. Ячейка с номером 9 свободна, значит записываем туда наш ключ.<br />
<br />
Таким образом, основная особенность двойного хеширования состоит в том, что при различных <tex> k </tex> пара <tex> (h_1(k),h_2(k)) </tex> дает различные последовательности ячеек для исследования.<br />
<br />
===Простая реализация===<br />
Пусть у нас есть некоторый объект <tex> item </tex>, в котором определено поле <tex> key </tex>, от которого можно вычислить хеш-функции <tex> h_1(key)</tex> и <tex> h_2(key) </tex><br />
<br />
Так же у нас есть таблица <tex> table </tex> величиной <tex> m </tex>, состоящая из объектов типа <tex> item </tex>.<br />
<br />
'''Вставка'''<br />
'''function''' add('''Item''' item):<br />
x = h1(item.key)<br />
y = h2(item.key)<br />
'''for''' (i = 0..m) <br />
'''if''' table[x] == ''null''<br />
table[x] = item<br />
'''return''' <br />
x = (x + y) '''mod''' m <br />
table.resize()<span style="color:Green">// ошибка, требуется увеличить размер таблицы<br />
<br />
'''Поиск'''<br />
'''Item''' search('''Item''' key):<br />
x = h1(key)<br />
y = h2(key)<br />
'''for''' (i = 0..m)<br />
'''if''' table[x] != ''null''<br />
'''if''' table[x].key == key<br />
'''return''' table[x]<br />
'''else'''<br />
'''return''' ''null''<br />
x = (x + y) '''mod''' m <br />
'''return''' ''null''<br />
<br />
===Реализация с удалением===<br />
Чтобы наша хеш-таблица поддерживала удаление, требуется добавить массив <tex>deleted</tex> типов <tex>bool</tex>, равный по величине массиву <tex>table</tex>. Теперь при удалении мы просто будем помечать наш объект ''как удалённый'', а при добавлении как ''не удалённый'' и замещать новым добавляемым объектом. При поиске, помимо равенства ключей, мы смотрим, удалён ли элемент, если да, то идём дальше.<br />
<br />
'''Вставка'''<br />
'''function''' add('''Item''' item):<br />
x = h1(item.key)<br />
y = h2(item.key)<br />
'''for''' (i = 0..m) <br />
'''if''' table[x] == '''null''' '''or''' deleted[x]<br />
table[x] = item<br />
deleted[x] = '''false'''<br />
'''return''' <br />
x = (x + i * y) '''mod''' m <br />
table.resize()<span style="color:Green">// ошибка, требуется увеличить размер таблицы<br />
'''Поиск'''<br />
'''Item''' search('''Item''' key):<br />
x = h1(key)<br />
y = h2(key)<br />
'''for''' (i = 0..m) <br />
'''if''' table[x] != '''null'''<br />
'''if''' table[x].key == key '''and''' !deleted[x]<br />
'''return''' table[x]<br />
'''else'''<br />
'''return''' '''null'''<br />
x = (x + y) '''mod''' m <br />
'''return''' '''null'''<br />
<br />
'''Удаление'''<br />
'''function''' remove('''Item''' key):<br />
x = h1(key)<br />
y = h2(key)<br />
'''for''' (i = 0..m)<br />
'''if''' table[x] != '''null'''<br />
'''if''' table[x].key == key<br />
deleted[x] = '''true'''<br />
'''else''' <br />
'''return'''<br />
x = (x + y) '''mod''' m<br />
<br />
==Альтернативная реализация метода цепочек==<br />
В Java 8 для разрешения коллизий используется модифицированный метод цепочек. Суть его заключается в том, что когда количество элементов в корзине превышает определенное значение, данная корзина переходит от использования связного списка к использованию [[АВЛ-дерево|сбалансированного дерева]]. Но данный метод имеет смысл лишь тогда, когда на элементах хеш-таблицы задан [[Отношение порядка|линейный порядок]]. То есть при использовании данный типа <tex>\mathbf{int}</tex> или <tex>\mathbf{double}</tex> имеет смысл переходить к дереву поиска, а при использовании каких-нибудь ссылок на объекты не имеет, так как они не реализуют нужный интерфейс. Такой подход позволяет улучшить производительность с <tex>O(n)</tex> до <tex>O(\log(n))</tex>. Данный способ используется в таких коллекциях как HashMap, LinkedHashMap и ConcurrentHashMap.<br />
<br />
[[Файл:Hashing_in_Java8.png|500px|Хеширование в Java 8.]]<br />
<br />
==См. также==<br />
* [[Хеширование]]<br />
* [[Хеширование_кукушки|Хеширование кукушки]]<br />
* [[Идеальное_хеширование|Идеальное хеширование]]<br />
<br />
== Источники информации ==<br />
* Бакнелл Дж. М. «Фундаментальные алгоритмы и структуры данных в Delphi», 2003<br />
* Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд «Алгоритмы: построение и анализ», 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010.— Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)<br />
* Дональд Кнут. «Искусство программирования, том 3. Сортировка и поиск» {{---}} «Вильямс», 2007 г.{{---}} ISBN 0-201-89685-0<br />
* Седжвик Р. «Фундаментальные алгоритмы на C. Части 1-4. Анализ. Структуры данных. Сортировка. Поиск», 2003<br />
* [http://openjdk.java.net/jeps/180 Handle Frequent HashMap Collisions with Balanced Trees]<br />
* [http://en.wikipedia.org/wiki/Double_hashing Wikipedia {{---}} Double_hashing]<br />
* [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 Разрешение коллизий]<br />
* [http://rain.ifmo.ru/cat/view.php/vis/hashtables/hash-2001-2 Пример хеш таблицы]<br />
* [http://research.cs.vt.edu/AVresearch/hashing/double.php Пример хеш таблицы с двойным хешированием]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Хеширование]]<br />
[[Категория: Структуры данных]]</div>93.92.207.162