Questions: Hash Tables: Collision Resolution by Chaining

Question 1

A chained hash table has m=100 buckets and n=400 keys, distributed uniformly. What is the expected time to search for a key?

• A. O(1) — hashing always gives constant-time lookup regardless of how many keys are stored
• B. O(log n) — chains are kept sorted for binary search
• C. O(1 + n/m) — constant time to find the bucket, plus traversing an average chain of length 4
• D. O(n) — in the worst case all keys collide, so the average must be O(n)

Answer: (C)

Expected search time under chaining is O(1 + α) where α = n/m is the load factor. Here α = 400/100 = 4, so expected time is O(5) = O(n/m). Option A is the misconception: O(1) only holds when α is bounded by a constant. Option D confuses worst case (all keys collide) with expected case under uniform hashing.

Question 2

Why does deletion in a chained hash table avoid the 'tombstone marker' complication found in open addressing?

• A. Chaining rehashes immediately after every deletion, so no marker is needed
• B. Chaining does not support deletion; keys must remain until a full rehash
• C. Deleted nodes are simply unlinked from their chain, leaving other chains and probe sequences unaffected
• D. Chaining uses doubly-linked lists, and tombstones are only required in singly-linked structures

Answer: (C)

In open addressing, deleting a key from a probe sequence would break the chain for subsequent lookups — a tombstone marks the slot as 'was occupied' so probing continues past it. In chaining, each bucket's linked list is independent; removing a node from the list does not affect any other bucket or probe sequence. This is one of chaining's practical advantages over open addressing.

Question 3

In a chained hash table, inserting a new key always takes O(1) time regardless of the current load factor.

• T. True
• F. False

Answer: True

Insertion under chaining is O(1): compute the hash (O(1)) and prepend the new key to the front of the target bucket's list (O(1)). Unlike search, insertion never needs to traverse the chain — it always goes to the front. The load factor affects search and delete time (which must traverse the chain), but not insertion time.

Question 4

A chained hash table with load factor α = 8 will produce incorrect search results because the chains have overflowed.

• T. True
• F. False

Answer: False

Chaining degrades gracefully — there is no 'overflow.' When α = 8, expected search time is O(9), which is slow but correct. The linked lists grow without bound; they never become invalid. This is in contrast to open addressing, where performance degrades rapidly and fails entirely at α = 1. High α is a performance problem, not a correctness problem.

Question 5

Explain why implementations rehash a chained hash table when the load factor exceeds a threshold, rather than simply allowing chains to grow indefinitely.

Model answer: As α grows, expected chain length grows proportionally, degrading search from O(1) to O(n) in the extreme. Rehashing — allocating a larger array and redistributing keys — resets α to a low value, restoring O(1) expected performance. Although rehashing costs O(n) per event, it occurs infrequently enough that the amortized cost per insertion remains O(1).

The load factor is the single number governing performance: O(1 + α) search means doubling α doubles expected search time. Without rehashing, a table that starts efficient becomes a slow linear scan as more keys are inserted. The amortized analysis (doubling the array means rehashing occurs at sizes 1, 2, 4, 8, ... so the total work is O(1 + 2 + 4 + ... + n) = O(2n) = O(n) spread over n insertions) shows the strategy is efficient overall.