Изменения

Основная идея хеширования кукушки — использование двух хеш-функций вместо одной (далее <math>h_1(x)</math> и <math>h_2(x)</math>). Так же есть вариант алгоритма, в котором используются две хеш-таблицы, и первая хеш-функция указывает на ячейку из первой таблицы, а вторая — из второй. Рассмотрим алгоритмы функций add(x), delete(x) и exists(x).

# Если одна из ячеек с индексами <math>h_1(x)</math> или <math>h_2(x)</math> свободна, кладем в нее элемент. Переходим к шагу 7.

# Помечаем ячейку, в которую только что добавили элемент, как занятую.

# Смотрим ячейки с индексами <math>h_1(x)</math> и <math>h_2(x)</math>.

# Если в одной из них есть искомый элемент, просто помечаем эту ячейку как свободную.

# Смотрим ячейки с индексами <math>h_1(x)</math> и <math>h_2(x)</math>.

# Если в одной из них есть искомый элемент, возвращаем true.

# Иначе возвращаем false.

==Зацикливание==

Зацикливание может возникнуть при добавлении элемента. Пусть мы добавляем элемент <tex>x</tex>. И обе ячейки <math>h_1(x)</math> и <math>h_2(x)</math> заняты. Пусть, для определенности, элемент <tex>x</tex> положили в ячейку <math>h_1(x)</math>. Если в ходе перемещений элементов в таблице на очередном шаге мы опять хотим переместить элемент <tex>x</tex> в ячейку <math>h_1(x)</math> то значит произошло зацикливание