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
Want the full step-by-step worked solution? It's part of Premium - along with a worked solution for every question in the bank.
Asked at: Timed Mental-Math & Sequences, ETF Market-Making