Fast Insertion for Bucketized Cuckoo Hashing

Abstract

Bucketized cuckoo hashing is a practically efficient hash table scheme in which each object $u$ is stored in one of two buckets $h_1(u),h_2(u)$ of capacity $\ell$. For any bucket size $\ell\in\mb{N}$, there is a threshold $\hat{I}{\mu }^{\ast }(\ell )=(2/e{)}^{\ell }\mathrm{poly}(\ell )$ for which there exists a way to fill the hash table to any load factor less than $1-\hat{I}{\mu }^{\ast }$ with low probability of an error. Queries and deletions only need to check two buckets to find whether an object exists. Our contribution is to give a new insertion procedure for bucketized cuckoo hashing. For any $\hat{I}´\in [.99^{\ell },1]$, our algorithm can fill the hash table to load factor $1-\hat{I}\mu =1-(1+\hat{I}´)(\hat{I}{\mu }^{\ast })$ with an expected run time of $O(\hat{I}{´}^{-1}(\hat{I}{\mu }^{\ast }{)}^{-1})$ per insertion. This gives the first $\mathrm{poly}(\hat{I}{\mu }^{-1})$ insertion time bound, and the first $f(\hat{I}{\mu }^{-1})$ time bound for load factors that are very close to the optimal threshold. Additionally, our algorithm (which can be viewed as a variation of the classic random-walk algorithm) comes with a very strong amortized guarantee: it performs $O(1)$ amortized expected evictions per insertion. Furthermore, we show that the traditional random-walk algorithm cannot match this guarantee. Finally, our insertion protocol also comes with the feature that, for any key $u$ in the hash table, the query algorithm can \emph{guess} which of the two bins $h_1(u),h_2(u)$ the key $u$ is in with probability $1-o(1)$ of being correct. Thus positive queries can complete in $1+o(1)$ expected bin accesses.

FOCS 2026