Question 1254

The Hole Hides Four

An 8-slot table uses linear probing with h(k) = k mod 8. After inserting 12, 20, and 4 in that order the table looks like this:

Linear probing table before the deletion of key 20 0123 4567 12 20 4 all three hash to slot 4

remove(20) is implemented as "find the slot, write EMPTY into it". Which call breaks immediately afterwards?

A

insert(28) overwrites slot 6 and destroys the key 4

B

find(4) reports not found, even though 4 is still stored in slot 6

C

find(12) reports not found, because its run was cut

D

find(20) reports not found, which is the bug