Изменения

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

Каждая ячейка <tex>i</tex> массива <tex>H</tex> содержит указатель на начало [[Список|списка ]] всех элементов, хеш-код которых равен <tex>i</tex>, либо указывает на их отсутствие. Коллизии приводят к тому, что появляются списки размером больше одного элемента.

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

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

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

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

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

delete(j);

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

Пусть у нас есть некоторый объект <tex> item </tex>, в котором определено поле <tex> key </tex>, от которого можно вычислить хеш-функции <tex> \mathrm{h_1(key)}</tex> и <tex> \mathrm{h_2(key)} </tex>

'''function''' add('''Item''' item):

'''for''' (i = 0; i < ..m; i++) '''if''' table[x] == ''null'' table[x] = item

x = (x + y) '''mod ''' m table.resize() <span style="color:Green">//ошибка, требуется увеличить размер таблицы

'''Item''' search('''Item''' key):

'''for''' (i = 0; i < ..m; i++) '''if''' table[x] != ''null''

'''else''' '''return''''' null'' x = (x + y) '''mod ''' m '''return''''' null''

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

'''function''' add('''Item''' item):

'''for''' (i = 0; i < ..m; i++) '''if''' table[x] == '''null || ''' '''or''' deleted[x]

deleted[x] = '''false'''

x = (x + y) '''mod ''' m table.resize() <span style="color:Green">//ошибка, требуется увеличить размер таблицы

'''Item''' search('''Item''' key):

'''for''' (i = 0; i < ..m; i++) '''if''' table[x] != '''null''' '''if''' table[x].key == key && '''and''' !deleted[x]

'''return''' ''' null''' x = (x + y) '''mod ''' m '''return''' ''' null'''

'''function''' remove('''Item''' key):

'''for''' (i = 0; i < ..m; i++) '''if''' table[x] != '''null'''

deleted[x] = '''true'''

x = (x + y) '''mod ''' m

== Разрешение коллизий в Java 8Альтернативная реализация метода цепочек==В Java 8 для разрешения коллизий используется модифицированный метод цепочек. Суть его заключается в том, что когда количество элементов в бакете корзине превышает определенное значение, данный бакет данная корзина переходит от использования связного списка к использованию [[АВЛ-дерево|сбалансированного дерева]]. Но данный метод имеет смысл лишь тогда, когда на элементах хеш-таблицы задан [[Отношение порядка|линейный порядок]]. То есть при использовании данны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|400px500px|Хеширование в Java 8.]]

== Литература Источники информации ==

 ==Ссылки==* [http://openjdk.java.net/jeps/180 Handle Frequent HashMap Collisions with Balanced Trees]