Abstract
In kary cuckoo hashing, each of cn objects is associated with k random buckets in a hash table of size n. An lorientation is an assignment of objects to associated buckets such that each bucket receives at most l objects. Several works have determined load thresholds c^* = c^*(k,l) for kary cuckoo hashing; that is, for c < c^* an lorientation exists with high probability, and for c > c^* no lorientation exists with high probability.
A natural variant of kary cuckoo hashing utilizes double hashing, where, when the buckets are numbered 0,1,...,n1, the k choices of random buckets form an arithmetic progression modulo n. Double hashing simplifies implementation and requires less randomness, and it has been shown that double hashing has the same behavior as fully random hashing in several other data structures that similarly use multiple hashes for each object. Interestingly, previous work has come close to but has not fully shown that the load threshold for kary cuckoo hashing is the same when using double hashing as when using fully random hashing. Specifically, previous work has shown that the thresholds for both settings coincide, except that for double hashing it was possible that o(n) objects would have been left unplaced. Here we close this open question by showing the thresholds are indeed the same, by providing a combinatorial argument that reconciles this stubborn difference.
BibTeX  Entry
@InProceedings{mitzenmacher_et_al:LIPIcs:2018:8855,
author = {Michael Mitzenmacher and Konstantinos Panagiotou and Stefan Walzer},
title = {{Load Thresholds for Cuckoo Hashing with Double Hashing}},
booktitle = {16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)},
pages = {29:129:9},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770682},
ISSN = {18688969},
year = {2018},
volume = {101},
editor = {David Eppstein},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8855},
URN = {urn:nbn:de:0030drops88557},
doi = {10.4230/LIPIcs.SWAT.2018.29},
annote = {Keywords: Cuckoo Hashing, Double Hashing, Load Thresholds, Hypergraph Orientability}
}
Keywords: 

Cuckoo Hashing, Double Hashing, Load Thresholds, Hypergraph Orientability 
Collection: 

16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018) 
Issue Date: 

2018 
Date of publication: 

04.06.2018 