Является ли удаление менее дорогостоящим, если используется линейное зондирование, чем в случае отдельного сцепления?

Question

Как известно, для хеш-таблиц мы сначала вычисляем хеш-функцию.Тогда нам нужно позаботиться о столкновениях;случаи, когда два или более ключей должны быть вставлены в хэш с одним и тем же индексом.Два способа сделать это включают в себя отдельные цепочки и линейное зондирование.Мой вопрос еще раз, какой метод является менее дорогостоящим, когда дело доходит до удаления?

Моя первоначальная идея состоит в том, что, если кластеры при линейном зондировании велики, и мы хотим удалить какой-то ключ на ранней стадии в кластере,может оказаться дорогостоящим переустановить все ключи справа от удаленного ключа.

Является ли это утверждение, если оно вообще допустимо, достаточным основанием для предположения, что раздельное сцепление более эффективно при удалении, чем линейное зондирование?

Answer 1

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

Но в случае отдельного сцепления нам просто нужно удалить значение из связанного списка, и удаление значения из связанного списка намного проще, чем описанный выше процесс в случае линейного зондирования.