Таблица хэшей: почему удаление в сложной схеме адресации

Я пытаюсь понять открытый метод Addressing, я ссылаюсь на TMH Corman Books в этом разделе было сказано, что в открытой адресации удаление затруднено, я не могу полностью это понять, пункт в котором я Сложно застревает Удаление из хэш-таблицы с открытым адресом затруднено. Когда мы удаляем ключ из слота i, мы не можем просто отметить этот слот как пустой, сохранив в нем NIL. Это может сделать невозможным извлечение любого ключа k во время ввода, который мы проверили в слоте я и обнаружили, что он занят. Здесь я не могу это понять, я очень благодарен вам за вашу помощь. Я потратил столько времени на то, что все время боюсь этого. Пожалуйста, объясните мне пример.

Спасибо

Ответ 1

Предположим hash(x) = hash(y) = hash(z) = i. И предположим, что x был вставлен первым, затем y, а затем z.
В открытой адресации: table[i] = x, table[i+1] = y, table[i+2] = z.

Теперь предположим, что вы хотите удалить x и установите его на NULL.

Когда вы будете искать z, вы обнаружите, что hash(z) = i и table[i] = NULL, и вы вернете неверный ответ: z не находится в таблице.

Чтобы преодолеть это, вам нужно установить table[i] специальным маркером, указывающим на функцию поиска, чтобы продолжить просмотр индекса i+1, потому что там может быть элемент, в котором его хэш также i.

Ответ 2

В открытой схеме адресации поисковые запросы вызывают серию пробников до тех пор, пока не будет найден ключ или не будет найден пустой слот.

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

Обычным решением является удаление ключа путем маркировки его слота как доступного для-resuse-but-not-фактически пустого. Другими словами, добавляется заменяющий шаговый камень, чтобы цепи зондов с другими ключами не были обрезаны.

Надеюсь, это поможет вашему пониманию.

Ответ 3

Удаление из линейной пробной открытой адресной хеш-таблицы прост. В течение многих лет на странице Wikipedia Hash Table был псевдокод. Я не знаю, почему этого больше нет, но это постоянная ссылка, когда это было: Старая страница Hash Table Wikipedia, и здесь для вашего удобства находится псевдокод:

function remove(key)
 i := find_slot(key)
 if slot[i] is unoccupied
     return   // key is not in the table
 j := i
 loop
     j := (j+1) modulo num_slots
     if slot[j] is unoccupied
         exit loop
     k := hash(slot[j].key) modulo num_slots
     if (j > i and (k <= i or k > j)) or
        (j < i and (k <= i and k > j)) (note 2)
         slot[i] := slot[j]
         i := j
 mark slot[i] as unoccupied

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

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