Open Addressing (“Closed Hashing”)
The main idea of open addressing is to avoid the links needed for chaining by permitting only one item per slot, but allowing a key to be in multiple slots.
- search and insert follow a probe sequence of possible locations for key : until an empty spot is found.
Open Addressing implemented through Linear Probing.
However, delete becomes problematic, since we cannot leave an empty spot behind; the next search might otherwise not go far enough.
- Like if you delete a
- Idea 1: Move later items in the probe sequence forward.
- Idea 2: lazy deletion: Mark spot as deleted (rather than NIL) and continue searching past deleted spots.
So what actually happens with deletion?
It seems that Idea 2 is actually used in the real-world through what is called tombstone deletion, though Idea 1 can also be used.
Tombstone Deletion
In tombstone deletion, to remove an element, you replace the element with a marker called a tombstone that indicates “an element used to be here, but has since been removed.” Stackoverflow .
Ways to implement Open Addressing: