Отличный вопрос! Вы абсолютно правы в том, что простое удаление элемента из таблицы линейного зондирования может вызвать проблемы именно в той ситуации, о которой вы сообщаете.
Для этого есть несколько решений. Одним из них является использование удаление захоронения . При удалении надгробной плиты, чтобы удалить элемент, вы заменяете элемент маркером, который называется надгробная плита , который указывает «элемент, который был здесь, но с тех пор был удален». Затем, когда вы выполняете поиск, вы используете ту же процедуру, что и раньше: прыгайте в положение ha sh, затем продолжайте идти вперед, пока не найдете пустое место. Идея заключается в том, что надгробный камень не считается пустым местом, поэтому вы продолжите сканировать его, чтобы найти то, что ищете.
Чтобы количество надгробий было низким, есть хорошие методы, которые вы можете использовать, такие как перезапись надгробий во время вставок или глобальное восстановление таблицы, если число надгробий становится слишком большим.
Другой вариант - использовать хеширование Робин Гуда и удаление с обратным смещением . В хешировании Робин Гуда вы храните элементы в таблице таким образом, что они по существу сохраняют их отсортированными по их коду ha sh (обтекание в начале таблицы делает вещи немного сложнее, чем это, но это общая идея) , После этого при удалении вы можете сдвинуть элементы назад на одну точку, чтобы заполнить пробел в удаленном элементе, пока вы не нажмете пробел или элемент, который уже находится в нужном месте и не нуждается в перемещении.
Для получения более подробной информации, ознакомьтесь с этими слайдами лекций по линейному зондированию и хэшированию Робин Гуда .
Надеюсь, это поможет!