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