Questions: Hash Tables: Collision Resolution by Open Addressing

Question 1

A hash table uses linear probing. After inserting many keys, you delete one by simply setting its slot to empty. What is the most likely consequence?

• A. No consequence — the slot is now available and future insertions will work correctly
• B. Subsequent searches for keys that probed past this slot will terminate prematurely, failing to find them
• C. The load factor drops, which improves performance
• D. The next insertion at this position will automatically repair the probe sequence

Answer: (B)

Open addressing relies on unbroken probe sequences. If a key K was inserted by probing past slot S to reach slot T, then emptying slot S breaks the path — a search for K will probe to the empty S and conclude K is absent, even though K exists at T. This is why deletions use a tombstone marker: a special value that tells searches 'keep probing' but tells insertions 'you can reuse this slot.' Option A is the classic mistake students make when they forget that open addressing chains multiple keys through the same probe path.

Question 2

A hash table has load factor α = 0.9 using linear probing. Which adjustment would most dramatically improve lookup performance?

• A. Switch to a better hash function
• B. Resize the table to reduce α to around 0.5
• C. Sort the stored keys so binary search can be used
• D. Use longer keys to reduce hash collisions

Answer: (B)

For linear probing, expected probes per successful search scales roughly as (1 + 1/(1-α)²)/2. At α=0.9, this is ~50 probes; at α=0.5, it's ~2.5 probes — a 20× improvement. The load factor is the dominant performance lever. A better hash function helps marginally with clustering but cannot overcome the fundamental explosion caused by a table that is 90% full. Sorting is inapplicable since the whole point of hashing is O(1) access, not binary search.

Question 3

Double hashing eliminates both primary and secondary clustering, unlike linear or quadratic probing.

• T. True
• F. False

Answer: True

Primary clustering (from linear probing) occurs when keys that collide at the same initial slot pile into adjacent cells, creating long runs. Quadratic probing breaks this by spacing probes farther apart, but keys sharing the same initial hash value still follow the same probe sequence — secondary clustering. Double hashing uses a second independent hash function h₂(k) to determine step size, so even keys with the same h₁ value diverge onto different probe paths. Both clustering forms are eliminated, giving effectively uniform probing at the cost of slightly more computation per probe.

Question 4

A well-designed hash table using open addressing can safely maintain a load factor of 0.95 without significant performance degradation.

• T. True
• F. False

Answer: False

Open-addressing performance degrades sharply as load factor approaches 1. At α=0.95 with linear probing, expected probes per lookup can exceed 200 — effectively destroying O(1) behavior. This is why practical implementations resize (typically doubling the table) when α exceeds a threshold: 0.5–0.75 for linear probing, up to 0.75 for double hashing. Chaining-based tables tolerate higher load factors better because their probe sequences don't share the same fixed array.

Question 5

Why can't you simply empty a slot when deleting a key from an open-addressing hash table, and what is the standard solution?

Model answer: Because open addressing stores keys along probe sequences that pass through other slots. A key K inserted after probing past slot S now sits beyond S in the probe path. If S is emptied, any future search for K will reach S, see an empty slot, and conclude K is absent — a false negative. The standard solution is to mark deleted slots with a tombstone sentinel. Tombstones tell search to continue probing (the chain isn't broken) but tell insertion to reuse the space (it counts as empty for storage). Periodic resizing clears tombstones and rebuilds the table cleanly.

This is the central subtlety of open addressing that distinguishes it from chaining. In chaining, deleting a node from a linked list has no effect on other nodes. In open addressing, every slot is part of one or more probe paths for keys that may have displaced themselves here or probed past here. The tombstone approach preserves probe-path integrity for reads while recovering space for writes. Accumulated tombstones degrade performance because searches must probe past them, which is why resizing (not just deletion) is part of table maintenance.