On Worst-Case Robin Hood Hashing

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 ~ α n elements into a table of size n where each probe is independent and uniformly distributed over the table, and α < 1 is a constant. Let Mₙ be the maximum search time for any of the elements in the table. We show that with probability tending to one, Mₙ ∈ [ log₂ log n + σ, log₂ log n + τ ] for some constants σ, τ depending upon α 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.