Изменения

[[Image:cuckoo.png|thumb|Пример хеширования кукушки. Стрелки показывают второе возможное место элементов. Если нам надо будет вставить новый элемент на место А, то мы поместим А в его вторую ячейку, занятую В, а В переместим в его вторую ячейку, которая сейчас свободна. А вот помещение нового элемента на место Н не получится: так как Н — часть цикла, добавленный элемент будет вытеснен после прохода по циклу.]]

==Алгоритм==

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

'''Add''' — добавляет элемент с ключом <tex>x</tex> в хэш-таблицу

# Иначе запоминаем элемент из этой ячейки, кладем туда старый. Проверяем, не зациклились ли мы.

# Если не зациклились, то продолжаем данную процедуру поиска свободного места пока не найдем свободное место или зациклимся.

# Так же после добавления нужно увеличить размер таблицы в случае если она заполнена.

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

==Время работы алгоритма==

{{ Утверждение