Ищет ли в хеш-таблице значение, которого нет в O (n)? (линейное зондирование)

Question

Просто пытаюсь понять логику линейного зондирования.

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

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

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

Что я говорю, разве вам не нужно просматривать всю карту, чтобы действительно подтвердить, что ее там нет?

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

Редактировать: Что я имею в виду, глядя на эту картинку http://upload.wikimedia.org/wikipedia/commons/b/bf/Hash_table_5_0_1_1_1_1_0_SP.svg

Если Джон Смит удалени мы пытаемся найти Сандру Ди.

Или с линейной адресацией вы должны перемещать элементы так, чтобы не было дыр как таковых.т.е. если Джон Смит удален, элементы от 152 до 154 должны быть перемещены назад на одно место?Это действительно не видно в описании, но это может иметь некоторый смысл.За исключением случаев, когда Тэд Бейкер хэшировал до 154, а не 153, как описано.Требуется немного больше работы, чем я думал.

Можно просто добавить простой список в каждом сегменте.

Answer 1

В абсолютном наихудшем случае, да, алгоритм определения того, находится ли какой-либо элемент в таблице, равен O (n).Однако это никогда не произойдет в правильно управляемой хэш-таблице.

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

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

Answer 2

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

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

Предположим, три элемента {A0, A1, A2} имеют одинаковое значение Hash. Пусть {A0, A1} находится в Hashtable, а {A2} нет. Если мы удаляем A0, мы помечаем его для удаления. Когда мы выполняем поиск A2 (не в Hashtable), мы находим A0 (удаленный), затем мы перемещаемся в A1, который перемещаем в слот A0, и завершаем удаление. Мы переходим к следующему слоту (который может быть А2, или кандидат на слот А1 только что занимал), но находим его пустым, поэтому мы очищаем слот, который А1 только что освободил, и наша хэш-таблица возвращается в первоначальное состояние.

Answer 3

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

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

В конце концов, когда вы ищете элемент в хеш-таблице, вы будете выполнять только поиск maxProb.

Теперь, учитывая, что вы не разрешаете бесконечное число или N проб, где N - емкость хеш-таблицы, время работы будет равно O (x), где x - максимально допустимая проба в худшем случае.

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