394
правки
Изменения
→Алгоритм
==Алгоритм==
Основная идея хеширования кукушки — использование двух хеш-функций вместо одной (далее <mathtex>h_1(x)</mathtex> и <mathtex>h_2(x)</mathtex>). Так же есть вариант алгоритма, в котором используются две хеш-таблицы, и первая хеш-функция указывает на ячейку из первой таблицы, а вторая — из второй. Рассмотрим алгоритмы функций add(x), delete(x) и exists(x).
'''Add''' — добавляет элемент с ключом <tex>x</tex> в хэш-таблицу
# Если одна из ячеек с индексами <mathtex>h_1(x)</mathtex> или <mathtex>h_2(x)</mathtex> свободна, кладем в нее элемент. Переходим к шагу 7.
# Иначе произвольно выбираем одну из этих ячеек, запоминаем элемент, который там находится, помещаем туда новый.
# Смотрим в ячейку, на которую указывает другая хеш-функция от элемента, который запомнили, если она свободна, помещаем его в нее. Переходим к шагу 7.
'''Delete''' — удаляет элемент с ключом <tex>x</tex> из хэш-таблицы.
# Смотрим ячейки с индексами <mathtex>h_1(x)</mathtex> и <mathtex>h_2(x)</mathtex>.
# Если в одной из них есть искомый элемент, просто помечаем эту ячейку как свободную.
'''Exists''' — проверяет на наличие элемента <tex>x</tex> в хэш-таблице
# Смотрим ячейки с индексами <mathtex>h_1(x)</mathtex> и <mathtex>h_2(x)</mathtex>.
# Если в одной из них есть искомый элемент, возвращаем true.
# Иначе возвращаем false.
