2026/07/27 by Tolson Bell, William Kuszmaul
#cs.DS
Bucketized cuckoo hashing is a practically efficient hash table scheme in which each object u is stored in one of two buckets h1(u), h2(u) of capacity ℓ. For any bucket size ℓ∈\mbN, there is a threshold ε^*(ℓ)=(2/e)^\ellpoly(ℓ) for which there exists a way to fill the hash table to any load factor less than 1-ε^* 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 δ∈[.99^ℓ,1], our algorithm can fill the hash table to load factor 1-ε=1-(1+δ)(ε^*) with an expected run time of O(δ-1(ε^*)-1) per insertion. This gives the first poly(ε-1) insertion time bound, and the first f(ε-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 guess which of the two bins h1(u), h2(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.