Изменения

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

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

1 байт добавлено, 22:01, 24 апреля 2012
Зацикливание
# Иначе возвращаем false.
==Зацикливание== Зацикливание может возникнуть при добавлении элемента. Пусть мы добавляем элемент <tex>x</tex>. И обе ячейки <tex>h_1(x)</tex> и <tex>h_2(x)</tex> заняты. Пусть, элемент <tex>x</tex> положили в ячейку <tex>h_i(x)</tex>. Если в ходе перемещений элементов в таблице на очередном шаге мы опять хотим переместить элемент <tex>x</tex> в ячейку <tex>h_i(x)</tex>, чтобы в ячейку <tex>h_j(x)</tex> поместить какой-то <tex>y</tex>(а это значит что может произойти, если в ходе перемещений элемент <tex>x</tex> был перемещен в ячейку <tex>h_j(x) ~(i \ne j) </tex> и затем в ячейку <tex>h_j(x)</tex> перемещается какой-то <tex>y</tex>) , то значит произошло зацикливание.
Например зацикливание возникнет если добавить в хэш-таблицу 3 элемента <tex>x,y,z</tex> у которых <tex>h_1(x)</tex> = <tex>h_1(y)</tex> =<tex>h_1(z)</tex> и <tex>h_2(x)</tex> = <tex>h_2(y)</tex> = <tex>h_2(z)</tex> равны.
1302
правки

Навигация