Insertion time of random walk cuckoo hashing - Alan Frieze
From Katie Gentilello
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.