Изменения

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

Разрешение коллизий

73 байта убрано, 00:03, 13 июня 2013
м
Удаление элемента без пометок
|statement=Асимптотически время работы <tex>delete</tex> и <tex>find</tex> совпадают
|proof=
Заметим что указатель <tex>j</tex> в каждой итерации перемещается вперёд на <tex>q</tex> (с учётом рекурсивных вызовов <tex>delete</tex>). То есть этот алгоритм просто проходит последовательно пройдёт по цепочке начиная от удаляемого элемента до последнего - с какой-то позиции до конца, равно как и учётом вызова <tex>find</tex> в худшем случаесобственно для нахождения удаляемого элемента, мы посетим все ячейки цепи.
}}
Это учтено.
* В других цепочках не появятся дыры
Противное возможно только в том случае, если какой-то элемент был действительно удалён. Удаляем мы только последнюю ячейку в цепи, и если бы на её месте возникла дыра для сторонней цепочки, это бы означало что элемент, стоящий на <tex>q</tex> позиций назад, одновременно принадлежал нашей и другой цепочкам, что невозможно (однако такое рассуждение не сработает если расстояние между соседними элементами цепочки - переменная величина).
==Двойное хеширование==
308
правок

Навигация