Хеширование кукушки

Хеширование кукушки — один из способов борьбы с коллизиями при создании хеш-таблицы.

Алгоритм

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

Add

1. Если одна из ячеек с индексами [math]h_1(x)[/math] или [math]h_2(x)[/math] свободна, кладем в нее элемент. Переходим к шагу 7.
2. Иначе произвольно выбираем одну из этих ячеек, вытаскиваем оттуда элемент, помещаем туда новый.
3. Смотрим в ячейку, на которую указывает другая хеш-функция от только что вытащенного элемента, если она свободна, помещаем его в нее. Переходим к шагу 7.
4. Иначе вытаскиваем из этой ячейки элемент, кладем туда старый. Проверяем, не зациклились ли мы.
5. Если не зациклились, переходим к шагу 3.
6. Иначе выбираем 2 новые хеш-функции и перехешируем все добавленные элементы.
7. Помечаем ячейку, в которую только что добавили элемент, как занятую.

Delete

1. Смотрим ячейки с индексами [math]h_1(x)[/math] и [math]h_2(x)[/math].
2. Если в одной из них есть искомый элемент, просто помечаем эту ячейку как свободную.

Exists

1. Смотрим ячейки с индексами [math]h_1(x)[/math] и [math]h_2(x)[/math].
2. Если в одной из них есть искомый элемент, возвращаем true.
3. Иначе возвращаем false.