Insertion time of random walk cuckoo hashing - Alan Frieze

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.