Paper 2021/447

Explicit, Closed-form, General bounds for Cuckoo Hashing with a Stash

Abstract

Cuckoo Hashing is a dictionary data structure in which a data item is stored in a small constant number of possible locations. It has the appealing property that a data structure of size $2m$ can hold up to $n = \frac{1}{d} m$ elements for any constant $d > 1$; i.e. the data structure size is a small constant times larger than the combined size of all inserted data elements. However, the probability that a cuckoo hash table build fails is $\Theta(\frac{1}{m})$. This is too high for many applications, especially cryptographic applications and Oblivious RAM. An alternative proposal introduced by Kirsch et al. is to store elements which cannot be placed in the main table in a ``stash'', reducing the failure probability to $\mathcal{O}(m^{-(s+1)})$ where $s$ is any constant stash size. However, this analysis did not apply to super-constant $s$, and the bounds are asymptotic rather than explicit. Further works improved upon this, but either were not explicit, not closed-form or had limitations on the stash size. In this paper we present the first explicit, closed-form bounds for the failure probability of cuckoo hashing with a stash for general stash sizes.