Efficient d -ary Cuckoo Hashing at High Load Factors by Bubbling Up
William Kuszmaul, Michael Mitzenmacher · Society for Industrial and Applied Mathematics eBooks · 2025
A d-ary cuckoo hash table is an open-addressed hash table that stores each key x in one of d random positions h1 (x ), h 2(x ),…, hd(x ). In the offline setting, where all items are given and keys need only be matched to locations, it is possible to support a load factor of 1 — ϵ while using hashes. The online setting, where keys are moved as new keys arrive sequentially, has the additional challenge of the time to insert new keys, and it has not been known whether one can use d = O (ln ϵ-1) hashes to support poly(ϵ-1) expected-time insertions.