pipette
ENEnglish

A Sharp Analysis of Fixed Offset Hash Tables

Yuhao Guo, Seth Pettie, Chengzhang Wan

Preprint

En palabras de los autores

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.

Resultado principalLimitación que admiten los autores

Apareció: viernes, 23 de octubre. arXiv. Preprint, todavía sin revisión por pares.