{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T07:54:49Z","timestamp":1787385289929,"version":"build-2736575974"},"reference-count":31,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1996,10]]},"abstract":"<jats:p>We define a new simple and general model for hashing. The basic model together with several variants capture many natural (sequential and parallel) hashing algorithms and represent common hashing practice. Our main results exhibit tight tradeoffs between hash-table size and the number of applications of a hash function on a single key.<\/jats:p>","DOI":"10.1137\/s0097539793255722","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:43:31Z","timestamp":1109227411000},"page":"936-955","source":"Crossref","is-referenced-by-count":4,"title":["The Tree Model for Hashing: Lower and Upper Bounds"],"prefix":"10.1137","volume":"25","author":[{"given":"Joseph","family":"Gil","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Friedhelm Meyer","family":"Auf Der Heide","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Avi","family":"Wigderson","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,31]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(78)90014-5"},{"key":"R2","volume-title":"The probabilistic method","author":"Alon Noga","year":"1992"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(79)90045-X"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1137\/0212046"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1145\/1994.2205"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/29.5.436"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177729330"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539791194094"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0032018"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1145\/828.1884"},{"key":"R11","unstructured":"J. Gil, Ph.D. Thesis,  Lower bounds and algorithms for hashing and parallel processing, Hebrew University of Jerusalem, Jerusalem,  1990"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1994.1127"},{"key":"R13","unstructured":"Joseph Gil, Yossi Matias,  Fast hashing on a PRAM\u2014designing by expectation,  Proceedings of the Second Annual ACM-SIAM Symposium on Discrete Algorithms (San Francisco, CA, 1991), ACM, New York,  1991,  271\u2013280 1 095 8420800.68457"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"J. Gil, F. Meyer Auf Der Heide, A. Wigderson,  Not all keys can be hashed in constant time,  Proc. 1990 ACM Symposium on Theory of Computing, Association for Computing Machinery, New York,  1990,  244\u2013253","DOI":"10.1145\/100216.100247"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(90)90214-I"},{"key":"R16","volume-title":"Urn models and their application","author":"Johnson Norman L.","year":"1977"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"A. R. Karlin, E. Upfal,  Parallel hashing: An efficient implementation of shared memory,  Proc. 1986 ACM Symposium on Theory of Computing, Association for Computing Machinery, New York,  1986,  160\u2013168","DOI":"10.1145\/12130.12146"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(84)90036-1"},{"key":"R19","volume-title":"The art of computer programming. Volume 3","author":"Knuth Donald E.","year":"1973"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1974.11993556"},{"key":"R21","unstructured":"Y. Matias,  1990, personal communication"},{"key":"R22","doi-asserted-by":"crossref","unstructured":"Y. Matias, U. Vishkin,  Converting high probability into nearly-constant time: With applications to parallel hashing,  Proc. 1991 ACM Symposium on Theory of Computing, Association for Computing Machinery, New York,  1991,  307\u2013316, Technical report UMIACS-TR-91-65, Institute for Advanced Computer Studies, University of Maryland, College Park, MD, 1991","DOI":"10.1145\/103418.103453"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-69672-5"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(87)90040-X"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1137\/0217029"},{"key":"R26","doi-asserted-by":"crossref","unstructured":"M. Sipser,  A complexity theoretic approach to randomness,  Proc. 1983 ACM Symposium on Theory of Computing, Association for Computing Machinery, New York,  1983,  330\u2013335","DOI":"10.1145\/800061.808762"},{"key":"R27","doi-asserted-by":"crossref","unstructured":"L. J. Stockmeyer,  The complexity of approximate counting,  Proc. 1983 ACM Symposium on Theory of Computing, Association for Computing Machinery, New York,  1983,  118\u2013126","DOI":"10.1145\/800061.808740"},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1145\/359168.359175"},{"key":"R29","unstructured":"J. S. Vitter,  Analysis of coalesced hashing, Technical report, STAN-CS-80-817, Department of Computer Science, Stanford University, Stanford, CA,  1982, Ph.D. thesis"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1145\/322261.322274"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1145\/3828.3836"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539793255722","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:18:02Z","timestamp":1787336282000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539793255722"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,10]]},"references-count":31,"journal-issue":{"issue":"5","published-print":{"date-parts":[[1996,10]]}},"alternative-id":["10.1137\/S0097539793255722"],"URL":"https:\/\/doi.org\/10.1137\/s0097539793255722","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996,10]]}}}