Изменения

== Удаление элемента без пометок (==<div style="background-color: #ABCDEF; font-size: 16px; font-weight: bold; color: #000000; text-align: center; padding: 4px; border-style: solid; border-width: 1px;">Эта статья находится в разработке) ==!</div><includeonly>[[Категория: В разработке]]</includeonly>

Рассуждение будет описывать случай с линейным поиском хеша. Будем при удалении элемента сдвигать всё последующие на шаг <tex>q</tex> позиций назад. При этом:

Учитывая это будем действовать следующим образом: при поиске следующего элемента цепочки будем пропускать все ячейки с другим значением хеша, первый найденный элемент копировать в текущую ячейку, и затем рекурсивно его удалять. Если такой следующей ячейки нет, то текущий элемент можно просто удалить, сторонние цепочки при этом не разрушатся (кстати это неверно для чего нельзя сказать про случай квадратичного поиска).

|statement=Асимптотически время работы <tex>O(delete)=O(</tex> и <tex>find)</tex>совпадают

Заметим что указатель <tex>j</tex> в каждой итерации перемещается вперёд на <tex>q</tex> (с учётом рекурсивных вызовов <tex>delete</tex>). То есть этот алгоритм просто проходит по всей цепочкеначиная с какой-то позиции до конца, примерно равно как и <tex>find</tex>в худшем случае.

Случай зацикливания Вариант с зацикливанием мы не рассматриваем, поскольку если <tex>q</tex> взаимнопросто с размером хеш-таблицы, то для зацикливания в ней вообще не должно быть свободных позиций  Теперь докажем почему этот алгоритм работает. Собственно нам требуется сохранение трёх условий.* В редактируемой цепи не остаётся дырокДокажем по индукции. Если на данной итерации мы просто удаляем элемент (база), то после него ничего нет, всё верно. Если же нет, то вызванный в конце <tex>delete</tex> (см. псевдокод) заметёт созданную дыру (скопированный элемент), и сам, по предположению, новых не создаст.* Элементы, которые уже на своих местах, не должны быть сдвинуты.Это учтено.* В других цепочках не появятся дырыПротивное возможно только в том случае, если какой-то элемент был действительно удалён. Удаляем мы только последнюю ячейку в цепи, и если бы на её месте возникла дыра для сторонней цепочки, это бы означало что элемент, стоящий на <tex>q</tex> позиций назад, одновременно принадлежал нашей и другой цепочкам, что невозможно (однако такое рассуждение не сработает если расстояние между соседними элементами цепочки - переменная величина).