Хеш-таблица с открытой адресацией, без ленивого удаления (без надгробий)

Question

Можно ли без ленивого удаления (без надгробий) в хэш-таблицах с открытой адресацией разрешать конфликты, отличные от линейного зондирования (но все еще открытой адресации)?

При линейном зондировании существует алгоритм здесь .Интересно, есть ли алгоритм без ленивого удаления, когда мы имеем квадратичное зондирование / двойное хеширование?

Answer 1

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

Answer 2

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

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