Insertion time of random walk cuckoo hashing

Abstract

We consider the expected insertion time of Cuckoo Hashing when clashes are resolved randomly. We prove O(1) expected time insertion in two cases:

(i) d choices of location and location capacity one: joint with Tony Johansson. (ii) 2 choices of location and location capacity d: joint with Samantha Petti