Эффективный способ реализовать отложенное удаление в открытом хеше с использованием Java
Я реализую открытую хеш-таблицу с использованием квадратичного зонда. Моя база данных - Java String[] (мои объекты ограничены только строками). Для удаления я использую отложенное удаление, но хочу реализовать его действительно эффективно. Я уверен, что есть более элегантное решение, чем проведение нового массива флагов (активный / пустой / удаленный).
Я думал о назначении некоторой известной константной строки при удалении (например, "", пустая строка) и при необходимости, чтобы сравнить содержимое ячейки с указателем самой этой строки (используя == вместо String.equals). Таким образом, я знаю, что ячейка удалена, но активная ячейка может содержать строку любого типа (включая пустую), потому что она никогда не будет указывать на нашу постоянную.
Есть ли проблемы с моей идеей?
1 ответ
Используйте один массив Object
s, элементы могут быть null
(свободный слот), String
(полный слот) и специальные
private static final Object TOMBSTONE = new Object();
для лениво удаленных слотов.