Efficient way to implement lazy deletion in open hash using java

Question

I'm implementing an open hash table using quadratic probe. My data base is java String[] (my objects are limited only to strings). For deletion I use lazy deletion, but I want to implement it really efficient. I'm sure there is more elegant solution than holding a brand new array of flags (active / empty / deleted).

I thought of assigning some known constant string when deleting (for example "", the empty string), and when needed, to compare cell content to the pointer of that string itself (using == instead of String.equals). That way I know the cell is deleted but an active cell can hold any kind of string (including an empty one) because it will never point to our constant one.

Is there any problem with my idea?

Answer 1

Use a single array of Objects, elements can either be null (free slot), String (full slot) and special

private static final Object TOMBSTONE = new Object();

for lazily deleted slots.