Код, который вы привели, помечает ячейку как свободную (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) (точнее ≈ (1 + 1/(1-α))/2).Среднее число проверок неуспешного поиска — O(1/(1-α)).Вставка имеет ту же асимптотику, зависит от коэффициента заполнения α = n / SIZE.С могильниками:
Поиск и вставка остаются ожидаемо O(1) при ограниченном числе могильников; но по мере их накопления эффективность падает (эффективный α растёт).Если вы периодически реорганизуете таблицу (rehash) при достижении порога, то амортизированная стоимость реорганизаций распределяется по операциям, и средняя стоимость остаётся O(1).С реорганизацией (backshift):
Одна операция удаления в худшем случае может потребовать сдвинуть/переставить O(cluster_length) элементов — в худшем O(n).Тем не менее, при последовательности операций амортизированная стоимость удаления остаётся O(1) при поддержании α < 1. Интуитивно: каждый элемент перемещается нечасто (всего при небольшом числе операций на элемент выполняется маленькое число сдвигов), а общее число перемещений по последовательности операций линейно растёт с числом операций.Вывод: при корректном поддержании коэффициента заполнения (например α ≤ 0.7) все операции (поиск, вставка, удаление с корректной схемой) дают ожидаемую амортизированную сложность O(1). Если не очищать могильники, производительность может деградировать до O(n) на операцию.

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

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