Cuckoo hashing. Pagh, R. & Rodler, F. F. J Algorithms, 51(2):122–144, Academic Press, Inc., Duluth, MN, USA, 2004. doi abstract bibtex We present a simple dictionary with worst case constant lookup time, equaling the theoretical performance of the classic dynamic perfect hashing scheme of Dietzfelbinger et al. [SIAM J. Comput. 23 (4) (1994) 738-761]. The space usage is similar to that of binary search trees. Besides being conceptually much simpler than previous dynamic dictionaries with worst case constant lookup time, our data structure is interesting in that it does not use perfect hashing, but rather a variant of open addressing where keys can be moved back in their probe sequences. An implementation inspired by our algorithm, but using weaker hash functions, is found to be quite practical. It is competitive with the best known dictionaries having an average case (but no nontrivial worst case) guarantee on lookup time.
@Article{pagh04cuckoo,
author = {Pagh, Rasmus and Rodler, Flemming Friche},
title = {Cuckoo hashing},
journal = {J Algorithms},
year = {2004},
volume = {51},
pages = {122--144},
issn = {0196-6774},
abstract = {We present a simple dictionary with worst case constant lookup time, equaling the theoretical performance of the classic dynamic perfect hashing scheme of Dietzfelbinger et al. [SIAM J. Comput. 23 (4) (1994) 738-761]. The space usage is similar to that of binary search trees. Besides being conceptually much simpler than previous dynamic dictionaries with worst case constant lookup time, our data structure is interesting in that it does not use perfect hashing, but rather a variant of open addressing where keys can be moved back in their probe sequences. An implementation inspired by our algorithm, but using weaker hash functions, is found to be quite practical. It is competitive with the best known dictionaries having an average case (but no nontrivial worst case) guarantee on lookup time.},
address = {Duluth, MN, USA},
doi = {10.1016/j.jalgor.2003.12.002},
number = {2},
keywords = {data structures, dictionaries, experiments, hashing, information retrieval, searching; hashing with constant lookup and amortized storing},
owner = {Sebastian},
publisher = {Academic Press, Inc.},
timestamp = {2011.10.19},
}
Downloads: 0
{"_id":"L4RPjSDLeC4bNChjS","bibbaseid":"pagh-rodler-cuckoohashing-2004","authorIDs":[],"author_short":["Pagh, R.","Rodler, F. F."],"bibdata":{"bibtype":"article","type":"article","author":[{"propositions":[],"lastnames":["Pagh"],"firstnames":["Rasmus"],"suffixes":[]},{"propositions":[],"lastnames":["Rodler"],"firstnames":["Flemming","Friche"],"suffixes":[]}],"title":"Cuckoo hashing","journal":"J Algorithms","year":"2004","volume":"51","pages":"122–144","issn":"0196-6774","abstract":"We present a simple dictionary with worst case constant lookup time, equaling the theoretical performance of the classic dynamic perfect hashing scheme of Dietzfelbinger et al. [SIAM J. Comput. 23 (4) (1994) 738-761]. The space usage is similar to that of binary search trees. Besides being conceptually much simpler than previous dynamic dictionaries with worst case constant lookup time, our data structure is interesting in that it does not use perfect hashing, but rather a variant of open addressing where keys can be moved back in their probe sequences. An implementation inspired by our algorithm, but using weaker hash functions, is found to be quite practical. It is competitive with the best known dictionaries having an average case (but no nontrivial worst case) guarantee on lookup time.","address":"Duluth, MN, USA","doi":"10.1016/j.jalgor.2003.12.002","number":"2","keywords":"data structures, dictionaries, experiments, hashing, information retrieval, searching; hashing with constant lookup and amortized storing","owner":"Sebastian","publisher":"Academic Press, Inc.","timestamp":"2011.10.19","bibtex":"@Article{pagh04cuckoo,\n author = {Pagh, Rasmus and Rodler, Flemming Friche},\n title = {Cuckoo hashing},\n journal = {J Algorithms},\n year = {2004},\n volume = {51},\n pages = {122--144},\n issn = {0196-6774},\n abstract = {We present a simple dictionary with worst case constant lookup time, equaling the theoretical performance of the classic dynamic perfect hashing scheme of Dietzfelbinger et al. [SIAM J. Comput. 23 (4) (1994) 738-761]. The space usage is similar to that of binary search trees. Besides being conceptually much simpler than previous dynamic dictionaries with worst case constant lookup time, our data structure is interesting in that it does not use perfect hashing, but rather a variant of open addressing where keys can be moved back in their probe sequences. An implementation inspired by our algorithm, but using weaker hash functions, is found to be quite practical. It is competitive with the best known dictionaries having an average case (but no nontrivial worst case) guarantee on lookup time.},\n address = {Duluth, MN, USA},\n doi = {10.1016/j.jalgor.2003.12.002},\n number = {2},\n keywords = {data structures, dictionaries, experiments, hashing, information retrieval, searching; hashing with constant lookup and amortized storing},\n owner = {Sebastian},\n publisher = {Academic Press, Inc.},\n timestamp = {2011.10.19},\n}\n\n","author_short":["Pagh, R.","Rodler, F. F."],"key":"pagh04cuckoo","id":"pagh04cuckoo","bibbaseid":"pagh-rodler-cuckoohashing-2004","role":"author","urls":{},"keyword":["data structures","dictionaries","experiments","hashing","information retrieval","searching; hashing with constant lookup and amortized storing"],"metadata":{"authorlinks":{}}},"bibtype":"article","biburl":"https://git.bio.informatik.uni-jena.de/fleisch/literature/raw/master/group-literature.bib","creationDate":"2019-11-19T16:50:42.483Z","downloads":0,"keywords":["data structures","dictionaries","experiments","hashing","information retrieval","searching; hashing with constant lookup and amortized storing"],"search_terms":["cuckoo","hashing","pagh","rodler"],"title":"Cuckoo hashing","year":2004,"dataSources":["C5FtkvWWggFfMJTFX"]}