Хеш-таблицы: открытая адресация и удаление элементов

Question

Я пытаюсь понять открытую адресацию в хеш-таблицах, но есть один вопрос, на который нет ответов в моей литературе. Это касается удаления элементов в такой хеш-таблице, если используется квадратичное зондирование. Затем удаленный элемент заменяется элементом дозорного. Затем операция get () знает, что она должна идти дальше, и метод add () перезапишет первый найденный страж. Но что произойдет, если я захочу добавить элемент с ключом, который уже находится в хеш-таблице, но находится под стражей в проверочном пути? Вместо того, чтобы перезаписывать значение экземпляра тем же ключом, который уже находится в таблице, метод add () перезапишет страж. И затем у нас есть несколько элементов с одним и тем же ключом в хэш-таблице. Я вижу это как проблему, так как это стоит памяти, а также потому, что удаление элемента из хеш-таблицы просто удалит первый из них, так что элемент все еще может быть найден в таблице (т.е. он не удален).

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

Answer 1

Но что произойдет, если я захочу добавить элемент с ключом, который уже в хеш-таблице, но за дозорной в пути исследования? Вместо перезаписи значения экземпляра тем же ключом который уже находится в таблице, метод add () перезапишет дозорный.

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

Существует реализация хеш-таблицы на http://www.algolist.net/Data_structures/Hash_table/Open_addressing (HashMap.java). Его put() метод делает именно это. (Разрешение столкновений является линейным зондированием в ссылочном фрагменте, но я не думаю, что это важное отличие с точки зрения алгоритма.)

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

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

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

Да, это так. Вы должны искать, пока не найдете пустой элемент.

Как эта проблема решается на практике?

Я не слишком много знаю о реализации хеш-таблиц в реальной жизни. Я полагаю, что многие из них доступны в Интернете в проектах с открытым исходным кодом. Я только что проверил классы Hashtable и HashMap в Java. Оба используют цепочку вместо открытой адресации.

Answer 2

Извините за поздний ответ, но в Java есть пример хеш-таблицы с открытой адресацией: java.util.IdentityHashMap.

Также вы можете использовать GNU Trove Project . Все его карты - это хеш-таблицы с открытой адресацией, как описано на странице обзора .