Изменения
→Алгоритм
Основная идея хеширования кукушки — использование двух хеш-функций вместо одной (далее <tex>h_1(x)</tex> и <tex>h_2(x)</tex>). Также есть вариант алгоритма, в котором используются две хеш-таблицы, и первая хеш-функция указывает на ячейку из первой таблицы, а вторая — из второй. Рассмотрим алгоритмы функций add(x), remove(x) и contains(x).
Выберем 2 хэш-функции <tex>h_1(x)</tex> и <tex>h_2(x)</tex>(из [[Универсальное семейство хеш-функций | универсального семейства хэш-функций]]).
'''Add''' — добавляет элемент с ключом <tex>x</tex> в хэш-таблицу
# Если одна из ячеек с индексами <tex>h_1(x)</tex> или <tex>h_2(x)</tex> свободна, кладем в нее элемент. Переходим к шагу 7Проверяем, если хэш-таблица заполнена увеличиваем её размер.
# Иначе произвольно выбираем одну из этих ячеек, запоминаем элемент, который там находится, помещаем туда новый.
# Смотрим в ячейку, на которую указывает другая хеш-функция от элемента, который запомнили, если она свободна, помещаем его в нее. Переходим к шагу 7Проверяем, если хэш-таблица заполнена увеличиваем её размер.
# Иначе запоминаем элемент из этой ячейки, кладем туда старый. Проверяем, не зациклились ли мы.
# Если не зациклились, переходим к шагу 3то продолжаем искать свободное место для очередных элементов.# Иначе выбираем 2 новые хеш-функции(из [[Универсальное семейство хеш-функций | универсального семейства хэш-функций]]) и перехешируем все добавленные элементы.# Помечаем ячейку, в которую только что добавили элемент, как занятую.# Проверяем, если хэш-таблица заполнена увеличиваем её размер.
