394
правки
Изменения
→Алгоритм
# Иначе произвольно выбираем одну из этих ячеек, запоминаем элемент, который там находится, помещаем туда новый.
# Смотрим в ячейку, на которую указывает другая хеш-функция от элемента, который запомнили, если она свободна, помещаем его в нее. Переходим к шагу 7.
# Иначе запоминаем элемент из этой ячейки, кладем туда старый. Проверяем, не [[Время работы алгоритма|зациклились]] ли мы.
# Если не зациклились, переходим к шагу 3.
# Иначе выбираем 2 новые хеш-функции и перехешируем все добавленные элементы.
# Если в одной из них есть искомый элемент, возвращаем true.
# Иначе возвращаем false.
==Зацикливание==
Зацикливание может возникнуть при добавлении элемента. Пусть мы добавляем элемент x. И обе ячейки <math>h_1(x)</math> и <math>h_2(x)</math> заняты. Пусть, для определенности, элемент x положили в ячейку <math>h_1(x)</math>. Если в ходе перемещений элементов в таблице на очередном шаге мы опять хотим переместить элемент x в ячейку <math>h_1(x)</math> то значит произошло зацикливание
Удаление и проверка происходят за <tex>O(1)</tex> (что является основной особенностью данного типа хеширования), добавление в среднем происходит за <tex>O(1)</tex>. Первые два утверждения очевидны: требуется проверить всего лишь 2 ячейки таблицы.
