Bounds on the Independence Required for Cuckoo Hashing

Content Provider	Semantic Scholar
Author	Kane, Daniel M.
Copyright Year	2013
Abstract	Cuckoo Hashing is an efficient dynamic hashing technique. It uses two hash functions and hashes each key to the value indicated by either one of the hash functions. This is known to take expected O(1) amortized time per operation as long as the hash functions are chosen independently and have at least Θ(lg n)-independence. This bound is not known to be tight, however, and this paper is an investigation of the degree of independence of the hash functions that will achieve the same guarantee. In particular, we show that a pair of 5-independent hash functions will not necessarily suffice, among other results.
File Format	PDF HTM / HTML
Alternate Webpage(s)	http://web.mit.edu/dankane/www/Independence%20Bounds.pdf
Alternate Webpage(s)	http://courses.csail.mit.edu/6.897/spring05/abstracts.pdf
Alternate Webpage(s)	http://web.mit.edu/jscohen/www/cuckoo.pdf
Alternate Webpage(s)	http://cseweb.ucsd.edu/~dakane/CuckooTalk.pdf
Alternate Webpage(s)	http://cseweb.ucsd.edu/~dakane/cuchkoohashing.pdf
Language	English
Access Restriction	Open
Content Type	Text
Resource Type	Article