ACO The ACO Seminar (2012-2013)

Apr 18, 3:30pm, Wean 8220
Daniel Kane, Stanford
Bounds on the independence required for Cuckoo Hashing


Cuckoo Hashing is a dynamic dictionary data structure that uses a pair of hash functions to deal with the problem of collisions. One of the disadvantages of this data structure is that the standard analysis requires that these hash functions be picked from log(n)-independent families in order to guarantee the standard runtime bounds. We investigate the necessity of this requirement, and show that not all 5-independent families of hash functions are sufficient for Cuckoo Hashing to work.

Back to the ACO home page