Изменения

Перейти к: навигация, поиск

Разрешение коллизий

4 байта добавлено, 23:30, 3 января 2019
Линейное разрешение коллизий
== Линейное разрешение коллизий ==
[[Файл:close_hash.png|thumb|380px|right|Пример хеш-таблицы с открытой адресацией и линейным пробированием.]]
Все элементы хранятся непосредственно в хеш-таблице, без использования связных списков. В отличие от хеширования с цепочками, при использовании этого метода может возникнуть ситуация, когда хеш-таблица окажется полностью заполненной, следовательно , будет невозможно добавлять в неё новые элементы. Так что при возникновении такой ситуации решением может быть динамическое увеличение размера хеш-таблицы, с одновременной её перестройкой.
=== Стратегии поиска ===
===Реализация с удалением===
Что бы Чтобы наша хеш-таблица поддерживала удаление, требуется добавить массив <tex>deleted</tex> типов <tex>bool</tex>, равный по величине массиву <tex>table</tex>. Теперь при удалении мы просто будем помечать наш объект ''как удалённый'', а при добавлении как ''не удалённый'' и замещать новым добавляемым объектом. При поиске, помимо равенства ключей, мы смотрим, удалён ли элемент, если да, то идём дальше.
'''Вставка'''
deleted[x] = '''false'''
'''return'''
x = (x + i * y) '''mod''' m
table.resize()<span style="color:Green">// ошибка, требуется увеличить размер таблицы
'''Поиск'''
==Альтернативная реализация метода цепочек==
В Java 8 для разрешения коллизий используется модифицированный метод цепочек. Суть его заключается в том, что когда количество элементов в корзине превышает определенное значение, данный данная корзина переходит от использования связного списка к использованию [[АВЛ-дерево|сбалансированного дерева]]. Но данный метод имеет смысл лишь тогда, когда на элементах хеш-таблицы задан [[Отношение порядка|линейный порядок]]. То есть при использовании данный типа <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.]]
1
правка

Навигация