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

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

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

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

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

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

которая требует перепроверки всех элементов цепочки ключа , то лучше вообще не удалять а 
 пере-создавать новую таблицу или отказаться от OA в пользу Separate Chaining.