Эффективный способ реализовать отложенное удаление в открытом хеше с использованием Java

Question

Я реализую открытую хеш-таблицу с использованием квадратичного зонда. Моя база данных - Java String[] (мои объекты ограничены только строками). Для удаления я использую отложенное удаление, но хочу реализовать его действительно эффективно. Я уверен, что есть более элегантное решение, чем проведение нового массива флагов (активный / пустой / удаленный).

Я думал о назначении некоторой известной константной строки при удалении (например, "", пустая строка) и при необходимости, чтобы сравнить содержимое ячейки с указателем самой этой строки (используя == вместо String.equals). Таким образом, я знаю, что ячейка удалена, но активная ячейка может содержать строку любого типа (включая пустую), потому что она никогда не будет указывать на нашу постоянную.

Есть ли проблемы с моей идеей?

Answer 1

Используйте один массив Objects, элементы могут быть null (свободный слот), String (полный слот) и специальные

private static final Object TOMBSTONE = new Object();

для лениво удаленных слотов.