{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,12]],"date-time":"2026-05-12T16:44:25Z","timestamp":1778604265888,"version":"3.51.4"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2012,6,1]],"date-time":"2012-06-01T00:00:00Z","timestamp":1338508800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2012,6]]},"abstract":"<jats:p>Randomized algorithms are often enjoyed for their simplicity, but the hash functions used to yield the desired theoretical guarantees are often neither simple nor practical. Here we show that the simplest possible tabulation hashing provides unexpectedly strong guarantees.<\/jats:p>\n          <jats:p>\n            The scheme itself dates back to Zobrist in 1970 who used it for game playing programs. Keys are viewed as consisting of\n            <jats:italic>c<\/jats:italic>\n            characters. We initialize\n            <jats:italic>c<\/jats:italic>\n            tables\n            <jats:italic>H<\/jats:italic>\n            1, ...,\n            <jats:italic>H<\/jats:italic>\n            <jats:italic>c<\/jats:italic>\n            mapping characters to random hash codes. A key\n            <jats:italic>x<\/jats:italic>\n            \u2009=\u2009(\n            <jats:italic>x<\/jats:italic>\n            <jats:sub>1<\/jats:sub>\n            , ...,\n            <jats:italic>x<\/jats:italic>\n            <jats:italic>c<\/jats:italic>\n            ) is hashed to\n            <jats:italic>H<\/jats:italic>\n            1[\n            <jats:italic>x<\/jats:italic>\n            1]\u2009\u2295\u2009\u22ef\u2009\u2295\u2009\n            <jats:italic>H<\/jats:italic>\n            <jats:italic>c<\/jats:italic>\n            [\n            <jats:italic>x<\/jats:italic>\n            <jats:italic>c<\/jats:italic>\n            ], where \u2295 denotes bit-wise exclusive-or.\n          <\/jats:p>\n          <jats:p>While this scheme is not even 4-independent, we show that it provides many of the guarantees that are normally obtained via higher independence, for example, Chernoff-type concentration, min-wise hashing for estimating set intersection, and cuckoo hashing.<\/jats:p>","DOI":"10.1145\/2220357.2220361","type":"journal-article","created":{"date-parts":[[2012,7,10]],"date-time":"2012-07-10T16:40:44Z","timestamp":1341938444000},"page":"1-50","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":43,"title":["The Power of Simple Tabulation Hashing"],"prefix":"10.1145","volume":"59","author":[{"given":"Mihai","family":"P\u01cetra\u015fcu","sequence":"first","affiliation":[{"name":"AT&amp;T Labs---Research"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mikkel","family":"Thorup","sequence":"additional","affiliation":[{"name":"AT&amp;T Labs---Research"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2012,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1545"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795288490"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 27th Symposium on Theoretical Aspects of Computer Science (STACS). 119--130","author":"Braverman V."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1690"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(79)90044-8"},{"key":"e_1_2_1_6_1","unstructured":"Cohen J. S. and Kane D. M. 2009. Bounds on the independence required for cuckoo hashing. Manuscript. http:\/\/math.stanford.edu\/~dankane\/cuchkoohashing.pdf. Cohen J. S. and Kane D. M. 2009. Bounds on the independence required for cuckoo hashing. Manuscript. http:\/\/math.stanford.edu\/~dankane\/cuchkoohashing.pdf."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/646511.695324"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_30"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 20th ACM\/SIAM Symposium on Discrete Algorithms (SODA). 795--804","author":"Dietzfelbinger M."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780634"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1997.0873"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.2307\/2314344"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1131"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/174130.174132"},{"key":"e_1_2_1_15_1","unstructured":"Knuth D. E. 1963. Notes on open addressing. Unpublished memorandum. http:\/\/citeseer.ist.psu.edu\/knuth63notes.html. Knuth D. E. 1963. Notes on open addressing. Unpublished memorandum. http:\/\/citeseer.ist.psu.edu\/knuth63notes.html."},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 19th ACM\/SIAM Symposium on Discrete Algorithms (SODA). 746--755","author":"Mitzenmacher M."},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"Motwani R. and Raghavan P. 1995. Randomized Algorithms. Cambridge University Press. Motwani R. and Raghavan P. 1995. Randomized Algorithms . Cambridge University Press.","DOI":"10.1017\/CBO9780511814075"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/070702278"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.002"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 37th International Colloquium on Automata, Languages and Programming (ICALP). 715--726","author":"P\u01cetra\u015fcu M."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/S089548019223872X"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701386216"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 11th ACM\/SIAM Symposium on Discrete Algorithms (SODA). 496--497","author":"Thorup M.","year":"2000"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/1496770.1496842"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/100800774"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(81)90033-7"},{"key":"e_1_2_1_27_1","unstructured":"Zobrist A. L. 1970. A new hashing method with application for game playing. Tech. rep. 88 Computer Sciences Department University of Wisconsin Madison WI. Zobrist A. L. 1970. A new hashing method with application for game playing. Tech. rep. 88 Computer Sciences Department University of Wisconsin Madison WI."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2220357.2220361","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2220357.2220361","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:00:46Z","timestamp":1750276846000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2220357.2220361"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,6]]},"references-count":27,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2012,6]]}},"alternative-id":["10.1145\/2220357.2220361"],"URL":"https:\/\/doi.org\/10.1145\/2220357.2220361","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,6]]},"assertion":[{"value":"2011-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-06-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}