Хеш-таблица: почему удаление сложно в открытой схеме адресации

Question

Я пытаюсь понять метод открытой адресации.Я ссылаюсь на книгу Т.Г. Кормена по этой теме, в которой говорится, что удаление в открытой адресации затруднено.Я полностью застрял в этом абзаце:

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

Answer 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.

Answer 2

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

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

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

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

Answer 3

Удаление из хеш-таблицы с открытым зондом с линейным зондированием является простым. На протяжении многих лет на странице хэш-таблицы Википедии существовал псевдокод. Я не знаю, почему его больше нет, но здесь есть постоянная ссылка на то, когда это было: Старая страница хеш-таблицы 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

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

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