Why tombstone bucket can be used for insertion?

user_1424739 0
Viewed 85

https://research.cs.vt.edu/AVresearch/hashing/deletion.php

The above webpage says this.

"If a tombstone is encountered when searching along a probe sequence, the search procedure continues with the search. When a tombstone is encountered during insertion, that slot can be used to store the new record."

I don't quite get why the second sentence works. Suppose, that three keys k1, k2, k3 all have the same hash. With open addressing linear probing, they are inserted to a hash table. The hash table buckets look like this. k1 is at the position pointed by the hash value.

... k1 k2 k3 ...

Now delete k1. The hash table becomes the following, where T indicates a tombstone.

... T k2 k3 ...

Then, I insert k3 again, it reaches T first then get it used, so I end up with two k3's in the hash table. This does not make sense to me.

... k3 k2 k3 ...

Could anybody explain why the second sentence makes sense?

associative-array hashmap data-structures dictionary hashtable
1 Answers

"Then, I insert k3 again" <- that's where you went wrong. When processing the second attempt to insert k3, you still have to search past the tombstone until you find an unused bucket, then if you hadn't seen k3 you'd go back and overwrite the tombstone instead of appending to the collision cluster at the unused bucket position.

Relating that to "When a tombstone is encountered during insertion, that slot can be used to store the new record." - it's not a simple if-then rule to apply during bucket-by-bucket iteration; it's only true in the bigger-picture sense that "during insertion" refers to the search past tombstones and existing but different elements until an unused bucket is found, and if indeed you do reach an unused bucket but had seen a tombstone, only then can you go back and overwrite the tombstone.

user_4107670
Related