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

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

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

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

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

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

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

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

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

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

Можно просто использовать простой связанный список в каждой корзине.