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

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 and Rodler. Random walk d-ary cuckoo hashing has low space overhead, guaranteed fast access, and fast in practice insertion time. In this paper, we give a theoretical insertion time bound for this algorithm. More precisely, for every d ≥ 3 random hashes, let c * d be the sharp threshold for the load factor at which a valid assignment of cm objects to a hash table of size m exists with high probability. We show that for any d ≥ 3 hashes and load factor c < c * d , the expectation of the random walk insertion time is O(1), that is, a constant depending only on d and c but not m.