Код, который вы привели, помечает ячейку как свободную $used=0$ и уходит. При линейном пробировании это ломает инвариант поиска — из‑за этого некоторые ключи «потеряются».

Почему это происходит $пример$

Пусть SIZE = 5, h$k1$ = 1, h$k2$ = 1.После вставок: table$$1$$ = k1, table$$2$$ = k2.Теперь вы удаляете k1 и делаете table$$1$$.used = 0.Поиск k2 начинает с h$k2$=1: встречает свободную ячейку table$$1$$ и решает, что k2 нет в таблице $петляforпрерывается$, хотя k2 находится в table$$2$$.
Причина: при поиске мы останавливаемся на первой пустой ячейке, считая, что дальше по цепочке от хэша ничего не могло оказаться. Но если при удалении освободить ячейку, эта гарантия нарушается.

Как исправить

1) Могильники $tombstones$

Вместо полного освобождения ячейки ставим специальный маркер "DELETED" $могильник$. Семантика:
Поиск: продолжает пробирование и через могильники $т.е.могильниксчитаетсяне‑пустойпосмыслупродолженияпоиска$.Вставка: при пробировании можно запомнить индекс первой встретившейся ячейки DELETED и в конце вставить туда $вместопустой$, чтобы переиспользовать могильник.Удаление: ставим метку DELETED вместо used = 0.Плюсы: простота, корректность поиска.Минусы: могильники накапливаются, ухудшая эффективность $эффективнаяплотностьувеличивается$. Нужно отслеживать число могильников и периодически выполнять реорганизацию $рехешвсейтаблицывновую,чтобыубратьвсеDELETED$ когда число DELETED слишком велико (например, > alpha_threshold * SIZE).

Псевдокод вставки с могильником:

first_deleted = -1for i = h$key$; table$$i$$.state != EMPTY; i = $i+1$%SIZE:
if table$$i$$.state == DELETED and first_deleted == -1: first_deleted = iif table$$i$$.state == OCCUPIED and table$$i$$.key == key: обновить/returnif first_deleted != -1: insert в first_deleted else insert в текущую EMPTY

2) Рееорганизация $backshift/реинсерциякластера$

После удаления освобождаем ячейку, но затем проходим дальше по цепочке и "подтягиваем" элементы влево, чтобы восстановить непрерывность кластера:
free = удалённая позицияj = $free+1$ % SIZEwhile table$$j$$.state == OCCUPIED:
k = table$$j$$.key; temp = table$$j$$table$$j$$.state = EMPTYвставить temp начиная с h$k$ $илипопробоватьпоставитьименновfree,еслидопустимо$free = новое место, откуда стало EMPTY $обычноfree=позиция,гдемывзялиэлемент$j = $j+1$%SIZEостановиться, когда встретили пустую ячейкуПроще и надёжнее вариант: после удаления последовательно извлекаете ключи из следующих занятых ячеек и "вставляете" их заново в таблицу до первой пустой ячейки.Такой подход убирает нужду в могильниках — таблица остаётся чистой.

Примечание по корректной реализации backshift: нужно аккуратно обработать круговую арифметику индексов; алгоритм гарантирует, что элементы останутся достижимы при поиске.

Амортизированная сложность

Для линейного пробирования при случайном $равномерном$ хэшировании:
Среднее число проверок успешного поиска — O$1$ $точнее\approx (1+1/(1-\alpha ))/2$.Среднее число проверок неуспешного поиска — O$1/(1-\alpha )$.Вставка имеет ту же асимптотику, зависит от коэффициента заполнения α = n / SIZE.С могильниками:
Поиск и вставка остаются ожидаемо O$1$ при ограниченном числе могильников; но по мере их накопления эффективность падает $эффективный\alpha растёт$.Если вы периодически реорганизуете таблицу $rehash$ при достижении порога, то амортизированная стоимость реорганизаций распределяется по операциям, и средняя стоимость остаётся O$1$.С реорганизацией $backshift$:
Одна операция удаления в худшем случае может потребовать сдвинуть/переставить O$cluste{r}_{l}ength$ элементов — в худшем O$n$.Тем не менее, при последовательности операций амортизированная стоимость удаления остаётся O$1$ при поддержании α < 1. Интуитивно: каждый элемент перемещается нечасто $всегопринебольшомчислеоперацийнаэлементвыполняетсямаленькоечислосдвигов$, а общее число перемещений по последовательности операций линейно растёт с числом операций.Вывод: при корректном поддержании коэффициента заполнения $например\alpha \le 0.7$ все операции $поиск,вставка,удалениескорректнойсхемой$ дают ожидаемую амортизированную сложность O$1$. Если не очищать могильники, производительность может деградировать до O$n$ на операцию.

Резюме / рекомендации

Нельзя просто ставить used = 0 — это ломает поиск.Проще реализовать: использовать могильники + периодический рехеш при накоплении DELETED.Более «чистый» вариант: после удаления реинсерировать/сдвигать элементы кластера $backshift$ — устраняет могильники, тоже корректен.Оба подхода при разумных порогах дают амортизированную O$1$ при случайном хэшировании и α < 1.