pipette
ESEspañol

A Sharp Analysis of Fixed Offset Hash Tables

Yuhao Guo, Seth Pettie, Chengzhang Wan

Preprint

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.