Изменения

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

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

10 байт убрано, 19:44, 6 июня 2012
Зацикливание
Зацикливание может возникнуть при добавлении элемента. Пусть мы добавляем элемент <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) ~(i \ne j) </tex> поместить какой-то <tex>y</tex> (это может произойти, если в ходе перемещений элемент <tex>x</tex> был перемещен в ячейку <tex>h_j(x)</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> равны.
==Время работы алгоритма==
Анонимный участник

Навигация