308
правок
Изменения
Нет описания правки
Учитывая это будем действовать следующим образом: при поиске следующего элемента цепочки будем пропускать все ячейки с другим значением хеша, первый найденный элемент копировать в текущую ячейку, и затем рекурсивно его удалять. Если такой следующей ячейки нет, то текущий элемент можно просто удалить, сторонние цепочки при этом не разрушатся (кстати это неверно для квадратичного поиска).
delete(i)
j = i + q
while table[j] == null || table[j].key != table[i].key
if (talbetable[j] == null)
table[i] = null
exit
delete(j);
{{Утверждение|about=== Время о времени работы |statement=<tex>O(delete)=O(find)</tex>|proof=Заметим что указатель <tex>j </tex> в каждой итерации перемещается вперёд на <tex>q </tex> (с учётом рекурсивных вызовов <tex>delete</tex>). То есть этот алгоритм просто проходит по всей цепочке, и асимптотика у delete такая же как у find.}}
Случай зацикливания мы не рассматриваем, поскольку если <tex>q </tex> взаимнопросто с размером хеш-таблицы, то для зацикливания в ней вообще не должно быть свободных элементов
==Двойное хеширование==
