A Sharp Analysis of Fixed Offset Hash Tables

Abstract

We consider the class of open addressing hash tables that uses a fixed offset sequence $r_0,r_1,\dots ,r_{n-1}$ to find an open slot in the table. As special cases this subsumes linear probing ($r_i=i$) and quadratic probing ($r_i=i^2$). We give a simple analysis that the expected insertion time when the load factor is $1-\epsilon$ is $O({\epsilon }^{-2})$. This bound is tight for linear probing (but not for quadratic probing), so the analysis cannot be improved at this level of generality.