Лучший способ удалить запись из хеш-таблицы
https://stackoverflow.com/questions/279539
-
07-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Как лучше всего удалить запись из хеш-таблицы, использующей линейное зондирование?Один из способов сделать это — использовать флаг для обозначения удаленных элементов?Есть ли способы лучше этого?
Решение
Простая техника заключается в следующем:
<Ол>Этот метод обеспечивает чистоту таблицы за счет более медленных удалений.
Другие советы
Это зависит от того, как вы справляетесь с переполнением, и от того, (1) находится ли удаляемый элемент в слоте переполнения или нет, и (2) есть ли элементы переполнения помимо удаляемого элемента, имеют ли они хеш-ключ удаляемый элемент или, возможно, какой-то другой хэш-ключ. [Пропуск двойного условия является распространенным источником ошибок в реализациях удаления.]
Если коллизии переполняются в связанный список, это довольно просто. Вы либо всплываете в списке (который может быть пустым), либо удаляете участника из середины или конца связанного списка. Это весело и не особенно сложно. Могут быть другие оптимизации, чтобы избежать чрезмерного выделения памяти и освобождения, чтобы сделать это еще более эффективным.
Для линейного зондирования Кнут предлагает простой способ пометить слот как пустой, удаленный или занятый. Пометьте удаленный слот-посетитель как удаленный, чтобы переполнение при линейном зондировании пропустило его, но если требуется вставка, вы можете заполнить первый удаленный слот, который вы пропустили [Искусство компьютерного программирования, том 3: Сортировка и поиск , раздел 6.4 Хеширование, с. 533 (ред.2)]. Это предполагает, что удаления довольно редки.
Кнут дает хорошее уточнение в качестве алгоритма R6.4 [стр. 533-534], который вместо этого помечает ячейку как пустую, а не как удаленную, а затем находит способы переместить записи таблицы обратно ближе к их исходному положению зонда, перемещая только что сделанное отверстие, пока оно не окажется рядом с другим отверстием.
Кнут предупреждает, что это переместит существующие все еще занятые записи слотов и не является хорошей идеей, если указатели на слоты удерживаются за пределами хэш-таблицы. [Если у вас есть собранные в мусоре или другие управляемые ссылки в слотах, все в порядке, если вы перемещаете слот, так как это ссылка, которая используется за пределами таблицы, и не имеет значения, где находится слот, который ссылается тот же объект находится в таблице.]
Реализация хеш-таблицы в Python (очень быстро спорная) использует фиктивные элементы для обозначения удалений. По мере того как вы увеличиваете или уменьшаете размер таблицы (если вы не используете таблицу фиксированного размера), вы можете одновременно отбрасывать макеты.
Если у вас есть доступ к копии, посмотрите статью в реализация Beautiful Code о реализации p.
Лучшие общие решения, которые я могу придумать, включают:
- Если вы можете использовать неконстантный итератор (например, C++ STL или Java), вы сможете удалить его по мере обнаружения.Однако, по-видимому, вы не задали бы этот вопрос, если бы не использовали константный итератор или перечислитель, который станет недействительным, если базовая коллекция будет изменена.
- Как вы сказали, вы можете пометить удаленный флаг внутри содержащегося объекта.Однако это не освобождает память и не уменьшает коллизий на ключе, поэтому это не лучшее решение.Также требуется добавление свойства в класс, которое, вероятно, ему не принадлежит.Если вас это беспокоит так же, как и меня, или если вы просто не можете добавить флаг к хранимому объекту (возможно, вы не контролируете класс), вы можете сохранить эти флаги в отдельной хеш-таблице.Это требует максимально долговременного использования памяти.
- Вставьте ключи элементов, подлежащих удалению, в список векторов или массивов, просматривая хеш-таблицу.После освобождения перечислителя пройдите по этому вторичному списку и удалите ключи из хеш-таблицы.Если вам нужно удалить много элементов и/или ключи большие (чего быть не должно), это может быть не лучшим решением.
- Если вы собираетесь удалить из хеш-таблицы больше элементов, чем оставляете, возможно, лучше создать новую хэш-таблицу и по мере прохождения исходной таблицы добавлять в новую хэш-таблицу только предметы, которые вы собираетесь сохранить.Затем замените ссылку(и) на старую хеш-таблицу новой.Это экономит повторение вторичного списка, но, вероятно, это эффективно только в том случае, если новая хеш-таблица будет содержать значительно меньше элементов, чем исходная, и это определенно работает только в том случае, если вы, конечно, можете изменить все ссылки на исходную хеш-таблицу.
- Если ваша хеш-таблица предоставляет вам доступ к своей коллекции ключей, вы можете перебирать их и удалять элементы из хеш-таблицы за один проход.
- Если ваша хеш-таблица или какой-либо помощник в вашей библиотеке предоставляет вам модификаторы коллекции на основе предикатов, у вас может быть функция Remove(), которой вы можете передать лямбда-выражение или указатель функции для идентификации элементов, которые нужно удалить.
Обычная техника, когда время является фактором, - это иметь вторую таблицу удаленных элементов и очищать основную таблицу, когда у вас есть время. Обычно используется в поисковых системах.
Как насчет того, чтобы расширить хеш-таблицу, чтобы она содержала указатели, например, связанный список? Когда вы вставляете, если корзина заполнена, создайте указатель из этой корзины на корзину, где хранится новое поле.
При удалении чего-либо из хеш-таблицы решение будет эквивалентно тому, как вы пишете функцию для удаления узла из связного списка.
