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
Collections
- ARC Talks and Events [88]