Hashing

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 $k$ to be in multiple slots.

• search and insert follow a probe sequence of possible locations for key $k$: $⟨h(k,0),h(k,1),h(k,2),...⟩$ 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.

• 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:

• Linear Probing
• Double Hashing
• Cuckoo Hashing