Какова стоимость удаления значения из хеш-таблицы?
Теперь у меня есть этот вопрос, где меня спросили стоимость удаления значения из хеш-таблицы, когда мы использовали линейное зондирование во время процесса вставки.
Из того, что я читал в Интернете, я мог понять, что это связано с коэффициентом загрузки. Хотя я не уверен, но я прочитал соотношение между коэффициентом нагрузки и не требуется ни одного зонда, и это не Количество зондов = 1 / (1-LF).
Поэтому я считаю, что стоимость должна зависеть от последовательности исследования. Но потом другая мысль все разрушает.
Что, если элемент был вставлен в p-зонды, и теперь я пытаюсь удалить этот элемент. Но до этого я уже удалил несколько элементов, имеющих одинаковый хэш-код, и был частью вставки в пробах меньше p.
В этом случае я достигаю стадии, когда я вижу пустой слот в хэш-таблице, но я не уверен, что элемент, который я пытаюсь удалить, уже удален или находится в каком-то другом месте в результате проверки.
Я также обнаружил, что после удаления элемента я должен пометить этот слот каким-то специальным индикатором, чтобы сообщить, что он доступен, но это не решает мою проблему неопределенности относительно элемента, который я хочу удалить.
Кто-нибудь может подсказать, пожалуйста, как найти стоимость в таких случаях? Будет ли подход меняться, если это нелинейное зондирование?
1 ответ
Стандартный подход - "искать элемент, пометить как удаленный". Очевидно, что разметка имеет стоимость O(1), поэтому общая стоимость операции такая же, как и при поиске: ожидаемая O(1). В вырожденных случаях он может достигать O (n) (например, все элементы имеют одинаковый хэш). O(1) ожидаемое это все, что мы можем сказать теоретически.
По поводу коэффициента загрузки. Чем выше коэффициент загрузки (отношение количества занятых сегментов к общему количеству), тем больше ожидаемый коэффициент (но это не меняет теоретическую стоимость O). Обратите внимание, что в этом случае коэффициент загрузки включает в себя количество элементов, присутствующих в элементах таблицы, плюс количество сегментов, помеченных как удаленные ранее.
Другие виды измерений (например, квадратичные) не изменяют теоретическую стоимость, но могут изменять ожидаемый постоянный коэффициент или его дисперсию. Если вы посмотрите на "резервные" последовательности, то в линейном порядке последовательности разных сегментов перекрываются. Это означает, что если для некоторого сегмента последовательность длинная, то для соседних сегментов она также будет длинной. Например: если сегменты с 4 по 10 заняты, последовательность для сегмента № 4 имеет длину 7 сегментов (4, 5, 6, ..., 10), для № 5 - 6 и так далее. Для квадратичного зондирования это не так.
Однако линейное зондирование имеет преимущество в улучшении поведения кэша памяти, поскольку вы проверяете ячейки памяти близко друг к другу. На практике, однако, для квадратичного зондирования резервные последовательности редко бывают достаточно длинными, чтобы это имело значение.
Наконец, в случае линейного зондирования можно работать без удаленной метки, но для этого вам придется значительно усложнить процедуру удаления (хотя все еще ожидается O(1), но с гораздо более высоким постоянным коэффициентом). Стоит ли оно того, должно быть решено с фактическим профилированием; например, это несколько упрощает вставку и поиск. Для реализации C++ это будет иметь обратную сторону: erase() сделает недействительными итераторы.