1632
правки
Изменения
м
ВремяВ зависимости от того нужна ли нам уникальность значений операции вставки у нас будет работать за разное время. Если не важна, то мы используем список, необходимое для время вставки в наихудшем который будет в худшем случае равно равна <tex>O(1)</tex>. Это операция выполняет быстро, так как считаетсяИначе мы проверяем есть ли в списке данный элемент, что вставляемый элемент отсутствует а потом в таблице, но если потребуется, то перед вставкой случае его отсутствия мы можем выполнить поиск этого его добавляем. В таком случае вставка элемента.в худшем случае будет выполнена за <tex>O(n)</tex>
'''for''' (i = 0; i < ..m; i++) '''if''' table[x] == '''null''' table[x] = item
'''else''' '''return''' '''null''' x = (x + y) '''mod''' m '''return''' '''null'''
Что бы Чтобы наша хеш-таблица поддерживала удаление, требуется добавить массив <tex>deleted</tex> типов <tex>bool</tex>, равный по величине массиву <tex>table</tex>. Теперь при удалении мы просто будем помечать наш объект ''как удалённый'', а при добавлении как ''не удалённый'' и замещать новым добавляемым объектом. При поиске, помимо равенства ключей, мы смотрим, удалён ли элемент, если да, то идём дальше.
'''function''' add('''Item''' item):
'''Item''' search('''Item''' key):
'''function''' remove('''Item''' key):
x = (x + y) '''mod ''' m
==Ссылки==
rollbackEdits.php mass rollback
'''Разрешение [[Хеш-таблица|коллизий]]''' (англ. collision resolution) в [[Хеш-таблица|хеш-таблице]], задача, решаемая несколькими способами: метод цепочек, открытая адресация и т. Напримерд. Очень важно сводить количество коллизий к минимуму, при помощи метода цепочке или открытой адресации. Коллизии замедляют так как это увеличивает время работы с хеш-таблицой, поэтому с ними нужно боротьсятаблицами.
== Разрешение коллизий с помощью цепочек ==
Каждая ячейка <tex>i</tex> массива <tex>H</tex> содержит указатель на начало [[Список|списка]] всех элементов, хеш-код которых равен <tex>i</tex>, либо указывает на их отсутствие. Коллизии приводят к тому, что появляются списки размером больше одного элемента.
Время работы поиска в наихудшем случае пропорционально длине списка, а если все <tex>n</tex> ключей захешировались в одну и ту же ячейку (создав список длиной <tex>n</tex>) время поиска будет равно <tex>\Theta(n)</tex> плюс время вычисления хеш-функции, что ничуть не лучше, чем использование связного списка для хранения всех <tex>n</tex> элементов.
== Линейное разрешение коллизий ==
[[Файл:close_hash.png|thumb|380px|right|Пример хеш-таблицы с открытой адресацией и линейным пробированием.]]
Все элементы хранятся непосредственно в хеш-таблице, без использования связных списков. В отличии отличие от хеширования с цепочками, при использовании этого метода может возникнуть ситуация, когда хеш-таблица окажется полностью заполненной, следовательно , будет невозможно добавлять в неё новые элементы. Так что при возникновении такой ситуации решением может быть динамическое увеличение размера хеш-таблицы, с одновременной её перестройкой.
=== Стратегии поиска ===
''' Псевдокод '''
'''function''' delete('''Item''' i) :
j = i + q
'''while''' table[j] == ''null'' '''nullor''' || table[j].key != table[i].key '''if''' (table[j] == '''null''') table[i] = '''null'''
'''return'''
j += q
table[i] = table[j]
delete(j);
Хеш-таблицу считаем зацикленной
|statement=Асимптотически время работы <tex>\mathrm{delete}</tex> и <tex>\mathrm{find}</tex> совпадают
|proof=
Заметим что указатель <tex>j</tex> в каждой итерации перемещается вперёд на <tex>q</tex> (с учётом рекурсивных вызовов <tex>\mathrm{delete}</tex>). То есть этот алгоритм последовательно пройдёт по цепочке от удаляемого элемента до последнего {{- --}} с учётом вызова <tex>\mathrm{find}</tex> собственно для нахождения удаляемого элемента, мы посетим все ячейки цепи.
}}
'''Вставка'''
'''function''' add('''Item''' item):
x = h1(item.key)
y = h2(item.key)
'''return'''
x = (x + y) '''mod''' m
'''Поиск'''
'''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]
===Реализация с удалением===
'''Вставка'''
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">//ошибка, требуется увеличить размер таблицы
'''Поиск'''
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'''
'''Удаление'''
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'''
== Разрешение коллизий в Java 8Альтернативная реализация метода цепочек==[[Файл:Hashing_in_Java8.png|thumb|400px|Хеширование в 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|500px|Хеширование в Java 8.]]
==См. также==
* [[Хеширование]]
* [[Хеширование_кукушки|Хеширование кукушки]]
* [[Идеальное_хеширование|Идеальное хеширование]]
== Литература Источники информации ==
* Бакнелл Дж. М. «Фундаментальные алгоритмы и структуры данных в Delphi», 2003
* Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд «Алгоритмы: построение и анализ», 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010.— Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)
* Дональд Кнут. «Искусство программирования, том 3. Сортировка и поиск» {{---}} «Вильямс», 2007 г.{{---}} ISBN 0-201-89685-0
* Седжвик Р. «Фундаментальные алгоритмы на C. Части 1-4. Анализ. Структуры данных. Сортировка. Поиск», 2003
* [http://openjdk.java.net/jeps/180 Handle Frequent HashMap Collisions with Balanced Trees]
* [http://en.wikipedia.org/wiki/Double_hashing Wikipedia {{---}} Double_hashing]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Хеширование]]
[[Категория: Структуры данных]]
