Изменения

'''Поиск свободного места при закрытом хешированииРазрешение [[Хеш-таблица|коллизий]]''' (англ. collision resolution) в [[Хеш-таблица|хеш- таблице]], задача, возникающая при создании решаемая несколькими способами: метод цепочек, открытая адресация и т.д. Очень важно сводить количество коллизий к минимуму, так как это увеличивает время работы с хеш-таблицы, использующей так называемое [[Открытое и закрытое хеширование#Закрытое хеширование|закрытое хеширование]]таблицами.

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

[[Файл:hashtables1.png|380px400px|Последовательный поиск, частный случай линейного поиска.]]

''' Линейный поиск '''

[[Файл:hashtables2Hashtables56.pngPNG|380px400px|Линейный поиск с шагом q.]]

''' Квадратичный поиск '''

[[Файл:hashtables3.png|380px400px|Квадратичный поиск.]] === Проверка наличия элемента в таблице===

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

== Проверка наличия элемента в таблице= Проблемы данных стратегий ===

Проверка осуществляется аналогично добавлениюПроблем две — крайне нетривиальное удаление элемента из таблицы и образование кластеров — последовательностей занятых ячеек. Кластеризация замедляет все операции с хеш-таблицей: мы проверяем ячейку при добавлении требуется перебирать всё больше элементов, при проверке тоже. Чем больше в таблице элементов, тем больше в ней кластеры и тем выше вероятность того, что добавляемый элемент попадёт в кластер.Для защиты от кластеризации используется двойное хеширование и [[Хеширование кукушки|хеширование кукушки]]. === Удаление элемента без пометок === Рассуждение будет описывать случай с линейным поиском хеша. Будем при удалении элемента сдвигать всё последующие на <tex>iq</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)  Хеш-таблицу считаем зацикленной  {{Утверждение|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>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> 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 ==Альтернативная реализация метода цепочек==В Java 8 для разрешения коллизий используется модифицированный метод цепочек. Суть его заключается в том, что когда количество элементов в корзине превышает определенное значение, данная корзина переходит от использования связного списка к использованию [[АВЛ-дерево|сбалансированного дерева]]. Но данный метод имеет смысл лишь тогда, когда на элементах хеш-таблицы задан [[Отношение порядка|линейный порядок]]. То есть при использовании данный типа <tex>\mathbf{int}</tex> или <tex>\mathbf{double}</tex> имеет смысл переходить к дереву поиска, а при использовании каких-нибудь ссылок на объекты не имеет, так как они не реализуют нужный интерфейс. Такой подход позволяет улучшить производительность с <tex>O(n)</tex> до <tex>O(\log(n))</pretex>. Данный способ используется в таких коллекциях как HashMap, LinkedHashMap и ConcurrentHashMap. [[Файл:Hashing_in_Java8.png|500px|Хеширование в 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]