The ACO Seminar (2012-2013)

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.