On Worst-Case Robin Hood Hashing
Luc Devroye, Pat Morin, Alfredo Viola · SIAM Journal on Computing · 2004
We consider open addressing hashing and implement it by using the Robin Hood strategy; that is, in case of collision, the element that has traveled the farthest can stay in the slot. We hash $\sim \alpha n$ elements into a table of size n where each probe is independent and uniformly distributed over the table, and $\alpha < 1$ is a constant. Let $M_n$ be the maximum search time for any of the elements in the table. We show that with probability tending to one, $M_n \in [ \log_2 \log n + \sigma, \log_2 \log n + \tau ]$ for some constants $\sigma, \tau$ depending upon $\alpha$ only. This is an exponential improvement over the maximum search time in case of the standard FCFS (firstcome first served) collision strategy and virtually matches the performance of multiple-choice hash methods.