O(1) Expected Insertion for Random Walk d-ary Cuckoo Hashing up to the Load Threshold

Tolson Bell, Alan Frieze

The random walk $d$-ary cuckoo hashing algorithm was defined by Fotakis, Pagh, Sanders, and Spirakis to generalize and improve upon the standard cuckoo hashing algorithm of Pagh an…