Как производить удаление элементов из хэш-таблицы правильно?

Для удаления элемента из хэш-таблицы правильно, следует выполнить следующие шаги:

1. Найти ячейку, в которой находится удаляемый элемент.
2. Если в этой ячейке хранится только од элемент, удалить его и пометить ячейку как пустую.
3. Если в этой ячейке есть другие элементы (коллизии), то необходимо определить, является ли удаляемый элемент последним в цепочке коллизий.
4. Если удаляемый элемент не является последним, то просто удалить его из цепочки коллизий.
5. Если удаляемый элемент последний в цепочке коллизий, то пометить ячейку как удаленную и перестроить цепочку коллизий (например, переместить предпоследний элемент в другую ячейку).

Для корректного удаления элемента 15 из цепочки коллизий 14 15 1 необходимо определить, что он является последним в цепочке. Затем пометить ячейку, в которой находится элемент 15, как свободную, и, возможно, переместить элемент 14 в другую ячейку (если она есть свободная).

Никак. Конечно, можно проверить, что там дальше ячейка пустая через k*k для всех возможных k (или что ячейка на (k-1)^2 назад пуста), но это слишком долго. И не сработает во всех случаях. Поэтому так и не делают вообще. Обычно "удаленные" значения убирают при перехешировании, которое все-равно придется делать при достаточном заполнении таблицы.

Судя по всему метод <b>открытой адресации</b> - это проосто нехороший метод для решения проблем хеширования. Я не знаю, толи преподаватели пошли очень душные. Толи студенты любопытные, но всех <br/> тянет как магнитом к open addressing (OA), хотя многие продуктовые библиотеки коллекций C++/C#/Java <br/> просто не используют OA по дефолту. Они берут Separate Chaining и это работает всегда хорошо. <br/> <br/> Я-бы сделал следующую рекомендацию. Поскольку удаление элемента при OA - <b>тяжелая операция,<br/>
которая требует перепроверки всех элементов цепочки ключа</b> , то лучше вообще не удалять а <br/> пере-создавать новую таблицу или отказаться от OA в пользу Separate Chaining.