В хэш таблице ячейка имеет три состояния: свободная, удалённая и занятая ключом.
Удаляя ключ, я должен пометить ячейку как удалённую или как свободную.
Поиск ключа в цепочке коллизий идёт до тех пор, пока не будет найден искомый ключ или свободная ячейка, удалённые пропускаются.
Если помечать каждую удаляемую ячейку как удалённую, то это приведёт к долгому или вовсе бесконечному поиску.
В итоге, удаляя ключ, ячейку в которой он был найден, я должен пометить свободной в том случае, если элемент является последним в цепочке коллизий, что-бы не прервать её.
Но я сталкиваюсь с такой проблемой во время определения того, является ли удаляемый элемент последним в цепочке коллизий:
Например, я помещаю ключ 2 в таблицу и он получает позицию 15, затем помещаю ключ 5 в таблицу, для него вычисляется позиция 14, но она занята неким элементом, далее квадратичным пробингом вычисляется позиция 15, она так-же занята, затем вычисляется позиция 1 и она свободна, он помещается в позицию 1.
Сейчас мы имеем, что элемент с ключом 2 находится в 15 позиции, а элемент с ключом 5 находится в позиции 1 и в цепочке коллизий 14 15 1.
Теперь, пытаясь удалить элемент с ключом 2 (в позиции 15) я не могу никак узнать, могу ли я отметить его ячейку как свободную.
Судя по всему метод открытой адресации - это проосто нехороший метод для решения проблем хеширования. Я не знаю, толи преподаватели пошли очень душные. Толи студенты любопытные, но всех
тянет как магнитом к open addressing (OA), хотя многие продуктовые библиотеки коллекций C++/C#/Java
просто не используют OA по дефолту. Они берут Separate Chaining и это работает всегда хорошо.
Я-бы сделал следующую рекомендацию. Поскольку удаление элемента при OA - тяжелая операция,
которая требует перепроверки всех элементов цепочки ключа, то лучше вообще не удалять а
пере-создавать новую таблицу или отказаться от OA в пользу Separate Chaining.
Вы обязаны проверять всю цепочку до тех пор пока
- не найдете нужный элемент
- не найдете пустое место
- пока идут надгробные камни
- пока вы не исчерпали лимит проверок. Например при размере OA hashtable например в
миллион элементов и при линейном опробировании вы можете по кругу пройти
всю адресную емкость таблицы.
Никак. Конечно, можно проверить, что там дальше ячейка пустая через k*k для всех возможных k (или что ячейка на (k-1)^2 назад пуста), но это слишком долго. И не сработает во всех случаях. Поэтому так и не делают вообще. Обычно "удаленные" значения убирают при перехешировании, которое все-равно придется делать при достаточном заполнении таблицы.
Герман, Кстати, оно не может быть очень редким. Оно случится ровно тогда, когда вы достаточное количество раз добавите элементы в таблицу. Оно обязательно случиться, если у вас элементов/"надгробий" (удаленных заглушек) станет в таблице слишком много. И оно при этом случится достаточно редко, чтобы амартизированно не ухудшать временную сложность добавления/удаления с O(1).
Средний
