Insertion time of random walk cuckoo hashing - Alan Frieze

From Katie Gentilello May 23rd, 2018

16 plays 0 comments

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

https://mediaspace.gatech.edu/media/frieze.mpg/1_u4hzrs6r

Tags: workshop on algorithms and randomnessalgorithms and randomness centergeorgia techrecorded by gtlibraryspring 2018

name: Alan Frieze
Date: May 15th, 2018
Appears In: Open Scholarship

Comments
Related Media

Loading…

Insertion time of random walk cuckoo hashing - Alan Frieze

Related Media