A further analysis of Cuckoo Hashing with a Stash and Random Graphs of Excess r
Reinhard Kutzelnigg
Abstract
Cuckoo hashing is a hash table data structure offering constant access
time, even in the worst case. As a drawback, the construction fails
with small, but practically significant probability. However, Kirsch
et al. (2008) showed that a constant-sized additional memory, the so
called stash, is sufficient to reduce the failure rate
drastically. But so far, using a modified insertion procedure that
demands additional running time to look for an admissible key is
required. As a major contribution of this paper, we show that the
same bounds on the failure probability hold even without this search
process and thus, the performance increases. Second, we extend the
analysis to simplified cuckoo hashing, a variant of the original
algorithm offering increased performance. Further, we derive some
explicit asymptotic approximations concerning the number of usual
resp. bipartite graphs related to the data structures. Using these
results, we obtain much more precise asymptotic expansions of the
success rate. These calculations are based on a generating function
approach and applying the saddle point method. Finally, we provide
numerical results to support the theoretical analysis.
Full Text: PDF PostScript