Лучший способ удалить запись из хеш-таблицы

Question

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

Answer 1

Простая техника:

1. Найдите и удалите нужный элемент
2. Перейти к следующему ведру
3. Если корзина пуста, выйти
4. Если корзина заполнена, удалите элемент из этой корзины и заново добавьте его в хеш-таблицу обычным способом. Элемент должен быть удален перед повторным добавлением, поскольку существует вероятность того, что элемент может быть добавлен обратно в исходное место.
5. Повторите шаг 2.

Этот метод обеспечивает чистоту таблицы за счет более медленных удалений.

Answer 2

Это зависит от того, как вы обрабатываете переполнение, и от того, (1) находится ли удаляемый элемент в слоте переполнения или нет, и (2) есть ли элементы переполнения помимо удаляемого элемента, имеют ли они хэш-ключ удаляемый элемент или, возможно, какой-то другой хэш-ключ. [Пропуск двойного условия является распространенным источником ошибок в реализациях удаления.]

Если столкновения переполняются в связанный список, это довольно легко. Вы либо всплываете в списке (который может быть пустым), либо удаляете участника из середины или конца связанного списка. Это весело и не особенно сложно. Могут быть другие оптимизации, чтобы избежать чрезмерного выделения памяти и освобождения, чтобы сделать это еще более эффективным.

Для линейного зондирования Кнут предлагает простой способ пометить слот как пустой, удаленный или занятый. Пометьте удаленный слот-посетитель как удаленный, чтобы переполнение при линейном зондировании пропустило его, но если требуется вставка, вы можете заполнить первый удаленный слот, который вы пропустили [Искусство компьютерного программирования, том 3: Сортировка и поиск , раздел 6.4 Хеширование, с. 533 (ред.2)]. Это предполагает, что удаления довольно редки.

Кнут дает хорошее уточнение как Алгоритм R6.4 [стр. 533-534], который вместо этого помечает ячейку как пустую, а не как удаленную, а затем находит способы переместить записи таблицы обратно ближе к их исходному положению зонда, перемещая только что сделанное отверстие, пока оно не окажется рядом с другим отверстием.

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

Answer 3

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

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

Answer 4

Лучшие общие решения, которые я могу придумать, включают:

• Если вы можете использовать неконстантный итератор (например, C ++ STL или Java), вы сможете удалить их по мере их появления. Предположительно, однако, вы бы не задавали этот вопрос, если бы не использовали константный итератор или перечислитель, который был бы недействительным, если базовая коллекция была изменена.
• Как вы сказали, вы можете пометить удаленный флаг внутри содержащегося объекта. Это не освобождает память и не уменьшает количество коллизий на ключе, так что это не лучшее решение. Также требует добавления свойства к классу, которое, вероятно, на самом деле не принадлежит там. Если это беспокоит вас так же сильно, как и меня, или если вы просто не можете добавить флаг к хранимому объекту (возможно, вы не управляете классом), вы можете сохранить эти флаги в отдельной хеш-таблице. Это требует самого длительного использования памяти.
• Вставьте ключи удаляемых элементов в список векторов или массивов при обходе хеш-таблицы. После освобождения перечислителя, переберите этот вторичный список и удалите ключи из хеш-таблицы. Если у вас есть много элементов, которые нужно удалить, и / или ключи большие (которых они не должны иметь), это может быть не лучшим решением.
• Если вы собираетесь в конечном итоге удалить из хеш-таблицы больше элементов, чем оставляете там, может быть лучше создать новую хеш-таблицу, и по мере того, как вы переходите к своей исходной, добавьте новый хеш-таблицу. стол только предметы, которые вы собираетесь сохранить. Затем замените ваши ссылки на старую хеш-таблицу новой. Это сохраняет вторичную итерацию списка, но, вероятно, она эффективна только в том случае, если в новой хеш-таблице будет значительно меньше элементов, чем в исходной, и она определенно работает, только если вы можете изменить все ссылки на исходную хеш-таблицу, конечно.
• Если ваша хеш-таблица дает вам доступ к ее коллекции ключей, вы можете выполнять их итерацию и удалять элементы из хеш-таблицы за один проход.
• Если ваша хеш-таблица или какой-либо помощник в вашей библиотеке предоставляют вам модификаторы коллекции на основе предикатов, у вас может быть функция Remove (), в которую вы можете передать лямбда-выражение или указатель функции, чтобы идентифицировать элементы для удаления.

Answer 5

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

Answer 6

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

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