A Sharp Analysis of Fixed Offset Hash Tables
In the authors' words
We consider the class of open addressing hash tables that uses a fixed offset sequence to find an open slot in the table. As special cases this subsumes linear probing () and quadratic probing (). We give a simple analysis that the expected insertion time when the load factor is is . This bound is tight for linear probing (but not for quadratic probing), so the analysis cannot be improved at this level of generality.
Main resultLimitation the authors admit
Appeared: Friday, October 23. arXiv. Preprint, not yet peer-reviewed.