Alfredo Viola: On Worst-Case Robin Hood Hashing

This is a joint work with Luc Devroye and Pat Morin from McGill University.

We consider open addressing hashing, and implement it by using the Robin Hood strategy, that is, in case of collision, the element that has travelled the furthest can stay in the slot.

We hash $\alpha n$ elements into a table of size $m$, 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 $\tau, \sigma$ depending upon $\alpha$ only.

This is an exponential improvement over the maximum search time in case of the standard FCFS (first come first served) collision strategy, and virtually matches the performance of multiple choice hash methods.

Back to the Index