A Sharp Analysis of Fixed Offset Hash Tables
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.