Изменения

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

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

18 байт убрано, 14:58, 23 апреля 2012
Зацикливание
==Зацикливание==
Зацикливание может возникнуть при добавлении элемента. Пусть мы добавляем элемент <tex>x</tex>. И обе ячейки <mathtex>h_1(x)</mathtex> и <mathtex>h_2(x)</mathtex> заняты. Пусть, для определенности, элемент <tex>x</tex> положили в ячейку <mathtex>h_1(x)</mathtex>. Если в ходе перемещений элементов в таблице на очередном шаге мы опять хотим переместить элемент <tex>x</tex> в ячейку <mathtex>h_1(x)</mathtex> то значит произошло зацикливание.
Например зацикливание возникнет если добавить в хэш-таблицу 3 элемента(x,y,z) у которых <mathtex>h_1(x)</mathtex> = <mathtex>h_1(y)</mathtex> =<mathtex>h_1(z)</mathtex> и <tex>h_2(x)</tex> = <mathtex>h_2(y)</mathtex> = <mathtex>h_2(xz)</mathtex> равны.
==Время работы алгоритма==
394
правки

Навигация