Hash Collisions, Deletion and Tombstones

Use a seven-slot table with h(key)=key MOD 7 and linear probing. Keys 10,17,24 all initially hash to slot 3, so insertion places them at 3,4,5. Lookup starts at the same initial slot and compares stored keys while following the same wrapped probe sequence. A matching hash alone does not establish that two keys are equal.

Probe at most the table’s capacity to avoid looping forever in a full table. Load factor affects expected work; expected constant-time operations depend on an appropriate hash distribution and occupancy. This simple modulo function is a teaching example, not a claim of good distribution for every real dataset. A different collision strategy needs a matching lookup strategy.

If key 17 is deleted by marking slot 4 as never-used empty, lookup for 24 can stop there and incorrectly report missing, even though 24 remains at slot 5. A tombstone marks a slot as deleted while preserving the instruction to continue searching. A true never-used empty slot can still terminate an unsuccessful lookup in this model.

Insertion can reuse a tombstone, but when unique keys are required it must first ensure that the same key is not already further down the probe chain. One approach remembers the first tombstone, continues checking until it finds the key or a true empty/end of probe, then inserts at the remembered slot if appropriate. Rebuilding a table can remove accumulated tombstones.

Separate chaining stores colliding entries in a bucket structure such as a linked list. Deleting one entry unlinks it from its bucket; lookup continues through the remaining bucket entries. It does not need an open-addressing tombstone merely because collisions exist. The bucket’s own traversal and update rules still matter.

When tracing operations, record distinct states for never used, occupied and deleted. State whether inserting an existing key replaces its value, rejects the insertion or permits duplicates; dictionaries commonly associate one current value with a key. Deletion of a missing key also needs a defined response. A table can contain unused capacity while lookup is slow if clustering or many tombstones force long probe sequences.

Attempt the task before opening its worked response. Record each change of state, explain the rule used, and check the result against the original requirements. Code examples labelled Python 3 use that language’s conventions; pseudocode states its own assumptions.