Random Walks for Cuckoo Hashing

February 4, 2009

We study the running time of a d-ary Cuckoo Hashing Table with a random insertion procedure. The Cuckoo Hashing Table uses d hash functions and guarantees that each key present be stored in one of the locations it hashes to. Cuckoo hashing is known to have good space efficiency and worst case access time, but insertion of items into the table is harder. A depth first search tree algorithm is known to take expected constant time, but its worst case performance can be polynomial. Most practical implementations use a random walk heuristic to insert items, which is known to work well in practice but previous to this work no theoretical bounds were known. We present an analysis of the random walk heuristic by analyzying matchings in random graphs, and show it runs in expected and worst case polylogarithmic time.