6.5 Особенности алгоритмов удаления записей из таблицы
 

Удаление из таблиц с однозначным соответствием между адресом в таблице и ключом не вызывает никаких трудностей, просто строка Т[а] с удаляемым ключом к помечается как свободная (поле ключа очищается).

Для таблиц с внешними цепочками переполнения в динамической памяти удаление является процедурой, обратной вставке, и выполняется аналогично операции удаления из обычного линейного списка. Корректируются значения указателей, и освобождается динамическая память. Однако если первый элемент по адресу а = f(к) хранится в самой хеш-таблице, то процедура удаления усложняется.

Для таблиц с линейной открытой адресацией при с = 1 придется переместить содержимое всех строк, следующих за удаляемой строкой, на одну позицию. Для всех остальных видов таблиц при удалении записи нарушается связь между синонимами. Чтобы этого не произошло, вместо ключа в строке удаляемой записи можно вписать специальный код. Тогда каждая строка хеш-таблицы находится в одном из трех состояний: свободном, занятом или удаленном. Строка из свободного состояния может перейти в занятое состояние, но освободившаяся строка не сможет перейти обратно в свободное состояние, если строка является промежуточным элементом цепочки. Взаимные переходы из занятого состояния в удаленное и обратно допустимы.

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