Изменения
Нет описания правки
'''Поиск свободного места при закрытом хешировании''' - задача, возникающая при создании хеш-таблицы, использующей так называемое [[Открытое и закрытое хеширование#Закрытое хеширование|закрытое хеширование]].
При использовании [[Открытое и закрытое хеширование#Открытое хеширование|открытого хеширования]] такой проблемы не возникает, так как там в каждой ячейке хранится список всех элементов. При добавлении необходимо просто дописать добавить элемент в конец начало списка.
[[Открытое и закрытое хеширование#Закрытое хеширование|Закрытое хеширование]] работает иначе: в каждой ячейке хеш-таблицы хранится только один элемент. Тогда при добавлении, если ячейка свободна, мы просто записываем добавляемый элемент в эту ячейку. Однако если эта ячейка занята - необходимо поместить добавляемый элемент в какую-нибудь другую свободную ячейку. Такие ситуации нередки, так как невозможно использовать хеш-функцию, не дающую коллизий, а каждой ячейке таблицы соответствует одно значение хеш-функции. Далее мы рассмотрим несколько стратегий поиска свободного места в данном случае.
Шаг <tex>q</tex> не фиксирован, а изменяется квадратично: <tex>q = 1,4,9,16...</tex>. Соответственно при попытке добавить элемент в занятую ячейку <tex>i</tex> начинаем последовательно просматривать ячейки <tex> i+1, i+4, i+9</tex> и так далее, пока не найдём свободную ячейку.
'' Возможные проблемы ''
При поиске элемента может получится так, что мы дойдём до конца таблицы. Обычно поиск продолжается, начиная с другого конца. Однако, если мы придём в ту ячейку, откуда начинался поиск, то добавить элемент в текущую таблицу будет невозможно и необходимо провести операцию перехеширования.
Если не осталось свободных ячеек то требуется увеличить размер хеш таблицы.
== Проверка наличия элемента в таблице==
Кластер - последовательность занятых клеток. Их наличие замедляет все операции с хеш-таблицей: при добавлении требуется перебирать всё больше элементов, при проверке тоже. Чем больше в таблице элементов, тем больше в ней кластеры и тем выше вероятность того, что добавляемый элемент попадёт в кластер.
Для защиты от кластеризации используется [[Двойное хеширование|двойное хеширование]] и [[Хеширование кукушки|хеширование кукушки]].
==Литература==
* ''Т. Кормен, Ч. Лейзерсон, Р. Ривест'': Алгоритмы: построение и анализ, 2-е изд
