Robin Hood Hashing really has constant average search cost and variance in full tables

Patricio V. Poblete, Alfredo Viola

Thirty years ago, the Robin Hood collision resolution strategy was introduced for open addressing hash tables, and a recurrence equation was found for the distribution of its searc…