Efficient $d$-ary Cuckoo Hashing at High Load Factors by Bubbling Up

William Kuszmaul, Michael Mitzenmacher

A $d$-ary cuckoo hash table is an open-addressed hash table that stores each key $x$ in one of $d$ random positions $h_1(x),h_2(x),\dots ,h_d(x)$. In the offline setting, where…