Изменения

Перейти к: навигация, поиск

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

223 байта убрано, 16:00, 7 июня 2012
Алгоритм
'''Add''' — добавляет элемент с ключом <tex>x</tex> в хэш-таблицу
# Если одна из ячеек с индексами <tex>h_1(x)</tex> или <tex>h_2(x)</tex> свободна, кладем в нее элемент. Проверяем, если хэш-таблица заполнена увеличиваем её размер.
# Иначе произвольно выбираем одну из этих ячеек, запоминаем элемент, который там находится, помещаем туда новый.
# Смотрим в ячейку, на которую указывает другая хеш-функция от элемента, который запомнили, если она свободна, помещаем его в нее. Проверяем, если хэш-таблица заполнена увеличиваем её размер.
# Иначе запоминаем элемент из этой ячейки, кладем туда старый. Проверяем, не зациклились ли мы.
# Если не зациклились, то продолжаем данную процедуру поиска свободного места пока не найдем свободное место или зациклимся.
Анонимный участник

Навигация