Probes in a colliding hash table

You insert the keys 21, 31, 41, 15, 2521,\ 31,\ 41,\ 15,\ 25 in that order into an initially empty hash table of size 1010. The hash is h(k)=kmod10h(k)=k \bmod 10, 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 11 probe. What is the total number of probes across all five insertions?

Show hints (2)+
  1. Three of the keys share home slot 11; two share slot 55. Simulate the table and watch each cluster grow.
  2. The home slot counts as probe 11; a run of kk colliding keys costs 1+2++k1+2+\cdots+k probes.

Answer

Reveal 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

Related questions