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

Ответ 1

Легкая техника заключается в следующем:

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

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

Ответ 2

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

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

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

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

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

Ответ 3

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

Если у вас есть доступ к копии, просмотрите статью в Beautiful Code о реализации.

Ответ 4

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

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

Ответ 5

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

Ответ 6

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

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