{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T06:02:06Z","timestamp":1775282526079,"version":"3.50.1"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2013,10,8]],"date-time":"2013-10-08T00:00:00Z","timestamp":1381190400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2014,11]]},"DOI":"10.1007\/s00453-013-9840-x","type":"journal-article","created":{"date-parts":[[2013,10,7]],"date-time":"2013-10-07T15:15:43Z","timestamp":1381158943000},"page":"428-456","source":"Crossref","is-referenced-by-count":19,"title":["Explicit and Efficient Hash Families Suffice for Cuckoo Hashing with a Stash"],"prefix":"10.1007","volume":"70","author":[{"given":"Martin","family":"Aum\u00fcller","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin","family":"Dietzfelbinger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Philipp","family":"Woelfel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2013,10,8]]},"reference":[{"key":"9840_CR1","unstructured":"Arbitman, Y.: Efficient dictionary data structures based on cuckoo hashing. Master\u2019s thesis, Weizmann Institute of Science (2010)"},{"issue":"2","key":"9840_CR2","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/0022-0000(79)90044-8","volume":"18","author":"L. Carter","year":"1979","unstructured":"Carter, L., Wegman, M.N.: Universal classes of hash functions. J. Comput. Syst. Sci. 18(2), 143\u2013154 (1979)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"9840_CR3","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1016\/S0020-0190(02)00500-8","volume":"86","author":"L. Devroye","year":"2003","unstructured":"Devroye, L., Morin, P.: Cuckoo hashing: Further analysis. Inf. Process. Lett. 86(4), 215\u2013219 (2003)","journal-title":"Inf. Process. Lett."},{"key":"9840_CR4","volume-title":"Graph Theory","author":"R. Diestel","year":"2005","unstructured":"Diestel, R.: Graph Theory. Springer, Berlin (2005)"},{"issue":"1","key":"9840_CR5","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1006\/jagm.1997.0873","volume":"25","author":"M. Dietzfelbinger","year":"1997","unstructured":"Dietzfelbinger, M., Hagerup, T., Katajainen, J., Penttonen, M.: A reliable randomized algorithm for the closest-pair problem. J. Algorithms 25(1), 19\u201351 (1997)","journal-title":"J. Algorithms"},{"key":"9840_CR6","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"354","DOI":"10.1007\/978-3-642-02927-1_30","volume-title":"Proc. 36th International Colloquium on Automata, Languages and Programming (ICALP)","author":"M. Dietzfelbinger","year":"2009","unstructured":"Dietzfelbinger, M., Rink, M.: Applications of a splitting trick. In: Proc. 36th International Colloquium on Automata, Languages and Programming (ICALP). LNCS, vol. 5555, pp. 354\u2013365. Springer, Berlin (2009)"},{"key":"9840_CR7","doi-asserted-by":"crossref","first-page":"795","DOI":"10.1137\/1.9781611973068.87","volume-title":"Proc. 20th ACM-SIAM Symp. on Discrete Algorithms (SODA)","author":"M. Dietzfelbinger","year":"2009","unstructured":"Dietzfelbinger, M., Schellbach, U.: On risks of using cuckoo hashing with simple universal hash classes. In: Proc. 20th ACM-SIAM Symp. on Discrete Algorithms (SODA), pp. 795\u2013804 (2009)"},{"issue":"1\u20132","key":"9840_CR8","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/j.tcs.2007.02.054","volume":"380","author":"M. Dietzfelbinger","year":"2007","unstructured":"Dietzfelbinger, M., Weidling, C.: Balanced allocation and dictionaries with tightly packed constant size bins. Theor. Comput. Sci. 380(1\u20132), 47\u201368 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"9840_CR9","first-page":"629","volume-title":"Proc. 35th ACM Symp. on Theory of Computing (STOC)","author":"M. Dietzfelbinger","year":"2003","unstructured":"Dietzfelbinger, M., Woelfel, P.: Almost random graphs with simple hash functions. In: Proc. 35th ACM Symp. on Theory of Computing (STOC), New York, NY, USA, pp. 629\u2013638 (2003)"},{"issue":"2","key":"9840_CR10","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1007\/s00224-004-1195-x","volume":"38","author":"D. Fotakis","year":"2005","unstructured":"Fotakis, D., Pagh, R., Sanders, P., Spirakis, P.G.: Space efficient hash tables with worst case constant access time. Theory Comput. Syst. 38(2), 229\u2013248 (2005)","journal-title":"Theory Comput. Syst."},{"key":"9840_CR11","doi-asserted-by":"crossref","first-page":"576","DOI":"10.1007\/978-3-642-22012-8_46","volume-title":"Proc. 38th International Colloquium on Automata, Languages and Programming (ICALP)","author":"M.T. Goodrich","year":"2011","unstructured":"Goodrich, M.T., Mitzenmacher, M.: Privacy-preserving access of outsourced data via oblivious ram simulation. In: Proc. 38th International Colloquium on Automata, Languages and Programming (ICALP), pp. 576\u2013587 (2011)"},{"key":"9840_CR12","series-title":"LNCS","first-page":"611","volume-title":"Proc. 16th European Symposium on Algorithms (ESA)","author":"A. Kirsch","year":"2008","unstructured":"Kirsch, A., Mitzenmacher, M., Wieder, U.: More robust hashing: cuckoo hashing with a stash. In: Proc. 16th European Symposium on Algorithms (ESA). LNCS, vol. 5193, pp. 611\u2013622. Springer, Berlin (2008)"},{"issue":"4","key":"9840_CR13","doi-asserted-by":"crossref","first-page":"1543","DOI":"10.1137\/080728743","volume":"39","author":"A. Kirsch","year":"2009","unstructured":"Kirsch, A., Mitzenmacher, M., Wieder, U.: More robust hashing: cuckoo hashing with a stash. SIAM J. Comput. 39(4), 1543\u20131561 (2009)","journal-title":"SIAM J. Comput."},{"key":"9840_CR14","series-title":"LNCS","first-page":"506","volume-title":"Proc. 10th Theoretical Informatics\u2014Latin American Symposium (LATIN)","author":"T.Q. Klassen","year":"2012","unstructured":"Klassen, T.Q., Woelfel, P.: Independence of tabulation-based hash classes. In: Proc. 10th Theoretical Informatics\u2014Latin American Symposium (LATIN). LNCS, vol. 7256, pp. 506\u2013517. Springer, Berlin (2012)"},{"issue":"3","key":"9840_CR15","first-page":"81","volume":"12","author":"R. Kutzelnigg","year":"2010","unstructured":"Kutzelnigg, R.: A further analysis of cuckoo hashing with a stash and random graphs of excess r. Discrete Math. Theor. Comput. Sci. 12(3), 81\u2013102 (2010)","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"9840_CR16","first-page":"746","volume-title":"Proc. 19th ACM-SIAM Symp. on Discrete Algorithms (SODA)","author":"M. Mitzenmacher","year":"2008","unstructured":"Mitzenmacher, M., Vadhan, S.P.: Why simple hash functions work: exploiting the entropy in a data stream. In: Proc. 19th ACM-SIAM Symp. on Discrete Algorithms (SODA), pp. 746\u2013755 (2008)"},{"issue":"2","key":"9840_CR17","doi-asserted-by":"crossref","first-page":"122","DOI":"10.1016\/j.jalgor.2003.12.002","volume":"51","author":"R. Pagh","year":"2004","unstructured":"Pagh, R., Rodler, F.F.: Cuckoo hashing. J. Algorithms 51(2), 122\u2013144 (2004)","journal-title":"J. Algorithms"},{"issue":"3","key":"9840_CR18","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1145\/2220357.2220361","volume":"59","author":"M. P\u01cetra\u015fcu","year":"2012","unstructured":"P\u01cetra\u015fcu, M., Thorup, M.: The power of simple tabulation hashing. J. ACM 59(3), 14 (2012)","journal-title":"J. ACM"},{"issue":"3","key":"9840_CR19","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1137\/S0097539701386216","volume":"33","author":"A. Siegel","year":"2004","unstructured":"Siegel, A.: On universal classes of extremely random constant-time hash functions. SIAM J. Comput. 33(3), 505\u2013543 (2004)","journal-title":"SIAM J. Comput."},{"key":"9840_CR20","first-page":"615","volume-title":"Proc. 15th ACM-SIAM Symp. on Discrete Algorithms (SODA)","author":"M. Thorup","year":"2004","unstructured":"Thorup, M., Zhang, Y.: Tabulation based 4-universal hashing with applications to second moment estimation. In: Proc. 15th ACM-SIAM Symp. on Discrete Algorithms (SODA), pp. 615\u2013624 (2004)"},{"issue":"2","key":"9840_CR21","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1137\/100800774","volume":"41","author":"M. Thorup","year":"2012","unstructured":"Thorup, M., Zhang, Y.: Tabulation-based 5-independent hashing with applications to linear probing and second moment estimation. SIAM J. Comput. 41(2), 293\u2013331 (2012)","journal-title":"SIAM J. Comput."},{"key":"9840_CR22","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1016\/0022-0000(81)90033-7","volume":"22","author":"M.N. Wegman","year":"1981","unstructured":"Wegman, M.N., Carter, L.: New hash functions and their use in authentication and set equality. J.\u00a0Comput. Syst. Sci. 22, 265\u2013279 (1981)","journal-title":"J.\u00a0Comput. Syst. Sci."},{"key":"9840_CR23","first-page":"424","volume-title":"Proc. 17th ACM-SIAM Symp. on Discrete Algorithms (SODA)","author":"P. Woelfel","year":"2006","unstructured":"Woelfel, P.: Asymmetric balanced allocation with simple hash functions. In: Proc. 17th ACM-SIAM Symp. on Discrete Algorithms (SODA), pp. 424\u2013433 (2006)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-013-9840-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-013-9840-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-013-9840-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:45:13Z","timestamp":1559137513000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-013-9840-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,10,8]]},"references-count":23,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2014,11]]}},"alternative-id":["9840"],"URL":"https:\/\/doi.org\/10.1007\/s00453-013-9840-x","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,10,8]]}}}