Probes in a colliding hash table
You insert the keys in that order into an initially empty hash table of size . The hash is , and collisions are resolved by linear probing (if a slot is taken, try the next slot to the right, wrapping around). Count a probe as each slot the insertion inspects, so landing in an empty home slot costs probe. What is the total number of probes across all five insertions?
Show hints (2)+
- Three of the keys share home slot ; two share slot . Simulate the table and watch each cluster grow.
- The home slot counts as probe ; a run of colliding keys costs probes.
Answer
Reveal answer →Final answer
9
Create a free account to see the full worked solution and track your progress.
Interview format: Numerical Reasoning Tests, ETF Trading