{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T13:37:12Z","timestamp":1770903432815,"version":"3.50.1"},"reference-count":108,"publisher":"Elsevier BV","issue":"1-2","license":[{"start":{"date-parts":[[1997,8,1]],"date-time":"1997-08-01T00:00:00Z","timestamp":870393600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":5829,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[1997,8]]},"DOI":"10.1016\/s0304-3975(96)00146-6","type":"journal-article","created":{"date-parts":[[2003,4,7]],"date-time":"2003-04-07T19:40:02Z","timestamp":1049744402000},"page":"1-143","source":"Crossref","is-referenced-by-count":95,"title":["Perfect hashing"],"prefix":"10.1016","volume":"182","author":[{"given":"Zbigniew J.","family":"Czech","sequence":"first","affiliation":[]},{"given":"George","family":"Havas","sequence":"additional","affiliation":[]},{"given":"Bohdan S.","family":"Majewski","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/S0304-3975(96)00146-6_BIB1","series-title":"The Design and Analysis of Computer Algorithms","author":"Aho","year":"1974"},{"key":"10.1016\/S0304-3975(96)00146-6_BIB2","series-title":"Proc. 27th Ann. Symp. on Foundations of Computer Science \u2014 FOCS'86","first-page":"55","article-title":"Storing a dynamic sparse table","author":"Aho","year":"1986"},{"key":"10.1016\/S0304-3975(96)00146-6_BIB3","series-title":"Principles of Compiler Design","author":"Aho","year":"1977"},{"issue":"2","key":"10.1016\/S0304-3975(96)00146-6_BIB4","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1145\/359060.359071","article-title":"Comments on perfect hashing functions: A single probe retrieving method for static sets","volume":"22","author":"Anderson","year":"1979","journal-title":"Comm. ACM"},{"key":"10.1016\/S0304-3975(96)00146-6_BIB5","series-title":"Proc. 17th Symp. on Mathematical Foundation of Computer Science \u2014 MFCS'92","first-page":"133","article-title":"A perfect parallel dictionary","volume":"Vol. 629","author":"Bast","year":"1992"},{"issue":"11","key":"10.1016\/S0304-3975(96)00146-6_BIB6","doi-asserted-by":"crossref","first-page":"924","DOI":"10.1145\/182.358446","article-title":"A Monte Carlo study of Cichelli hash-function solvability","volume":"26","author":"Bell","year":"1983","journal-title":"Comm. ACM"},{"key":"10.1016\/S0304-3975(96)00146-6_BIB7","series-title":"Programming Pearls","author":"Bentley","year":"1986"},{"key":"10.1016\/S0304-3975(96)00146-6_BIB8","series-title":"Random Graphs","author":"Bollob\u00e1s","year":"1985"},{"key":"10.1016\/S0304-3975(96)00146-6_BIB9","series-title":"Proc. 17th Ann. ACM Symp. on Theory of Computing \u2014 STOC'85","first-page":"224","article-title":"On the expected behaviour of disjoint set union algorithms","author":"Bollob\u00e1s","year":"1985"},{"issue":"10","key":"10.1016\/S0304-3975(96)00146-6_BIB10","doi-asserted-by":"crossref","first-page":"967","DOI":"10.1002\/spe.4380191005","article-title":"Near-perfect hashing of large word sets","volume":"19","author":"Brain","year":"1989","journal-title":"Software \u2014 Practice and Experience"},{"issue":"3","key":"10.1016\/S0304-3975(96)00146-6_BIB11","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1016\/0306-4379(90)90001-6","article-title":"Perfect hashing using sparse matrix packing","volume":"15","author":"Brain","year":"1990","journal-title":"Inform. Systems"},{"issue":"2","key":"10.1016\/S0304-3975(96)00146-6_BIB12","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1109\/69.277768","article-title":"Using tries to eliminate pattern collisions in perfect hashing","volume":"6","author":"Brain","year":"1994","journal-title":"IEEE Trans. Knowledge Data Eng."},{"key":"10.1016\/S0304-3975(96)00146-6_BIB13","series-title":"Algorithmics: Theory and Practice","author":"Brassard","year":"1988"},{"key":"10.1016\/S0304-3975(96)00146-6_BIB14","series-title":"Proc. 9th Ann. ACM Symp. on Theory of Computing \u2014 STOC'77","first-page":"106","article-title":"Universal classes of hash functions","author":"Carter","year":"1977"},{"key":"10.1016\/S0304-3975(96)00146-6_BIB15","series-title":"Proc. 20th Ann. Symp. on Foundations of Computer Science \u2014 FOCS'79","first-page":"175","article-title":"New classes and applications of hash functions","author":"Carter","year":"1979"},{"issue":"2","key":"10.1016\/S0304-3975(96)00146-6_BIB16","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/0022-0000(79)90044-8","article-title":"Universal classes of hash functions","volume":"18","author":"Carter","year":"1979","journal-title":"J. Computer System sci."},{"issue":"6","key":"10.1016\/S0304-3975(96)00146-6_BIB17","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1109\/MS.1985.232067","article-title":"An interactive system for finding perfect hash functions","volume":"2","author":"Cercone","year":"1985","journal-title":"IEEE Software"},{"key":"10.1016\/S0304-3975(96)00146-6_BIB18","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/0020-0255(84)90032-X","article-title":"An ordered minimal perfect hashing scheme based upon euler's theorem","volume":"32","author":"Chang","year":"1984","journal-title":"Inform. sci."},{"issue":"4","key":"10.1016\/S0304-3975(96)00146-6_BIB19","doi-asserted-by":"crossref","first-page":"384","DOI":"10.1145\/358027.358051","article-title":"The study of an ordered minimal perfect hashing scheme","volume":"27","author":"Chang","year":"1984","journal-title":"Comm. ACM"},{"key":"10.1016\/S0304-3975(96)00146-6_BIB20","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1016\/0020-0255(86)90024-1","article-title":"Letter-oriented reciprocal hashing scheme","volume":"38","author":"Chang","year":"1986","journal-title":"Inform. sci."},{"issue":"2","key":"10.1016\/S0304-3975(96)00146-6_BIB21","first-page":"173","article-title":"A composite perfect hashing scheme for large letter-oriented key sets","volume":"7","author":"Chang","year":"1991","journal-title":"J. Inform. sci. Engng."},{"issue":"2","key":"10.1016\/S0304-3975(96)00146-6_BIB22","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/0020-0190(88)90096-8","article-title":"An ordered minimal perfect hashing scheme with single parameter","volume":"27","author":"Chang","year":"1988","journal-title":"Inform. Process. Lett."},{"issue":"5","key":"10.1016\/S0304-3975(96)00146-6_BIB23","doi-asserted-by":"crossref","first-page":"469","DOI":"10.1093\/comjnl\/34.5.469","article-title":"On the design of a machine independent perfect hashing scheme","volume":"34","author":"Chang","year":"1991","journal-title":"Comput. J."},{"issue":"4","key":"10.1016\/S0304-3975(96)00146-6_BIB24","doi-asserted-by":"crossref","first-page":"530","DOI":"10.1007\/BF01990533","article-title":"A refinement of a compression-oriented addressing scheme","volume":"33","author":"Chang","year":"1993","journal-title":"BIT"},{"issue":"3","key":"10.1016\/S0304-3975(96)00146-6_BIB25","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1093\/comjnl\/29.3.277","article-title":"A letter-oriented minimal perfect hashing scheme","volume":"29","author":"Chang","year":"1986","journal-title":"Comput. J."},{"issue":"3\u20134","key":"10.1016\/S0304-3975(96)00146-6_BIB26","first-page":"275","article-title":"A fast Chinese characters accessing technique using mandarin phonetic transcriptions","volume":"3","author":"Chang","year":"1988","journal-title":"Comput. Process. Chinese Oriental Languages"},{"issue":"1","key":"10.1016\/S0304-3975(96)00146-6_BIB27","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1002\/spe.4380210104","article-title":"A letter-oriented perfect hashing scheme based upon sparse table compression","volume":"21","author":"Chang","year":"1991","journal-title":"Software \u2014 Practice Experience"},{"issue":"1","key":"10.1016\/S0304-3975(96)00146-6_BIB28","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1145\/358808.358813","article-title":"Minimal perfect hash functions made simple","volume":"23","author":"Cichelli","year":"1980","journal-title":"Comm. ACM"},{"issue":"9","key":"10.1016\/S0304-3975(96)00146-6_BIB29","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1145\/947955.947957","article-title":"A letter oriented minimal perfect hashing function","volume":"17","author":"Cook","year":"1982","journal-title":"SIGPLAN Notices"},{"issue":"1","key":"10.1016\/S0304-3975(96)00146-6_BIB30","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1093\/comjnl\/28.1.54","article-title":"Practical perfect hashing","volume":"28","author":"Cormack","year":"1985","journal-title":"Comput. J."},{"issue":"5","key":"10.1016\/S0304-3975(96)00146-6_BIB31","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1016\/0020-0190(92)90220-P","article-title":"An optimal algorithm for generating minimal perfect hash functions","volume":"43","author":"Czech","year":"1992","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/S0304-3975(96)00146-6_BIB32","first-page":"3","article-title":"Generating a minimal perfect hashing function in O(m2) time","volume":"4","author":"Czech","year":"1992","journal-title":"Archiwum Informatyki Teoretycznej i Stosowanej"},{"issue":"6","key":"10.1016\/S0304-3975(96)00146-6_BIB33","doi-asserted-by":"crossref","first-page":"579","DOI":"10.1093\/comjnl\/36.6.579","article-title":"A linear time algorithm for finding minimal perfect hash functions","volume":"36","author":"Czech","year":"1993","journal-title":"Comput. J."},{"issue":"1","key":"10.1016\/S0304-3975(96)00146-6_BIB34","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1145\/355984.355988","article-title":"Algorithms for generating fundamental cycles in a graph","volume":"8","author":"Deo","year":"1982","journal-title":"ACM Trans. Math. Software"},{"key":"10.1016\/S0304-3975(96)00146-6_BIB35","series-title":"Proc. 19th Internat. Colloq. on Automata, Languages and Programming \u2014 ICALP'92","first-page":"235","article-title":"Polynomial hash functions are reliable","volume":"Vol. 623","author":"Dietzfelbinger","year":"1992"},{"key":"10.1016\/S0304-3975(96)00146-6_BIB36_1","series-title":"Proc. 29th Ann. Symp. on Foundations of Computer Science \u2014 FOCS'88","article-title":"Dynamic perfect hashing: upper and lower bounds","author":"Dietzfelbinger","year":"1994"},{"issue":"4","key":"10.1016\/S0304-3975(96)00146-6_BIB36_2","first-page":"738","volume":"24","year":"1988","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0304-3975(96)00146-6_BIB37","series-title":"Proc. ACM Symp. on Parallel Algorithms and Architectures","first-page":"360","article-title":"An optimal parallel dictionary","author":"Dietzfelbinger","year":"1989"},{"key":"10.1016\/S0304-3975(96)00146-6_BIB38","series-title":"Proc. 22nd ACM Symp. on Theory of Computing \u2014 STOC'90","first-page":"117","article-title":"How to distribute a dictionary on a complete network","author":"Dietzfelbinger","year":"1990"},{"key":"10.1016\/S0304-3975(96)00146-6_BIB39","series-title":"Proc. 17th Internat. Colloq. on Automata, Languages and Programming \u2014 ICALP'90, Warwick University","first-page":"6","article-title":"A new universal class of hash functions, and dynamic hashing in real time","volume":"Vol. 443","author":"Dietzfelbinger","year":"1990"},{"key":"10.1016\/S0304-3975(96)00146-6_BIB40","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1006\/inco.1993.1007","article-title":"An optimal parallel dictionary","volume":"102","author":"Dietzfelbinger","year":"1993","journal-title":"Inform. and Comput."},{"issue":"3","key":"10.1016\/S0304-3975(96)00146-6_BIB41","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1109\/TSE.1983.236866","article-title":"The study of a new perfect hash scheme","volume":"SE-9","author":"Du","year":"1983","journal-title":"IEEE Trans. Software Eng."},{"key":"10.1016\/S0304-3975(96)00146-6_BIB42","first-page":"399","article-title":"Types of cycles in hypergraphs","volume":"27","author":"Duke","year":"1985","journal-title":"Ann. Discrete Math."},{"key":"10.1016\/S0304-3975(96)00146-6_BIB43_1","first-page":"17","article-title":"On the evolution of random graphs","volume":"5","author":"Erd\u00f6s","year":"1960","journal-title":"Publ. Math. Inst. Hung. Acad. sci."},{"key":"10.1016\/S0304-3975(96)00146-6_BIB43_2","series-title":"Mathematicians of Our Time","first-page":"574","article-title":"The art of counting: selected writings","author":"Erd\u00f6s","year":"1973"},{"key":"10.1016\/S0304-3975(96)00146-6_BIB44_1","first-page":"343","article-title":"On the evolution of random graphs","volume":"38","author":"Erd\u00f6s","year":"1961","journal-title":"Bull. Inst. Internat. Statis."},{"key":"10.1016\/S0304-3975(96)00146-6_BIB44_2","series-title":"Mathematicians of Our Time","first-page":"569","article-title":"The art of counting: selected writings","author":"Erd\u00f6s","year":"1973"},{"key":"10.1016\/S0304-3975(96)00146-6_BIB45","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1016\/0012-365X(89)90087-3","article-title":"The first cycles in an evolving graph","volume":"75","author":"Flajolet","year":"1989","journal-title":"Discrete Math."},{"issue":"3","key":"10.1016\/S0304-3975(96)00146-6_BIB46","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1145\/125187.125200","article-title":"Order preserving minimal perfect hash functions and information retrieval","volume":"9","author":"Fox","year":"1991","journal-title":"ACM Trans. Inform. Systems"},{"key":"10.1016\/S0304-3975(96)00146-6_BIB47","series-title":"Proc. 15th Ann. Internat. ACM SIGIR Conf. on Research and Development in Information Retrieval \u2014 SIGIR'92","first-page":"266","article-title":"A faster algorithm for constructing minimal perfect hash functions","author":"Fox","year":"1992"},{"key":"10.1016\/S0304-3975(96)00146-6_BIB48","article-title":"An O(n log n) algorithm for finding minimal perfect hash functions","author":"Fox","year":"1989"},{"issue":"1","key":"10.1016\/S0304-3975(96)00146-6_BIB49","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1145\/129617.129623","article-title":"Practical minimal perfect hash functions for large databases","volume":"35","author":"Fox","year":"1992","journal-title":"Comm. ACM"},{"issue":"3","key":"10.1016\/S0304-3975(96)00146-6_BIB50","doi-asserted-by":"crossref","first-page":"538","DOI":"10.1145\/828.1884","article-title":"Storing a sparse table with O(1) worst case access time","volume":"31","author":"Fredman","year":"1984","journal-title":"J. ACM"},{"key":"10.1016\/S0304-3975(96)00146-6_BIB51","series-title":"Computers and Intractibility: A Guide to the Theory of NP-completeness","author":"Garey","year":"1979"},{"issue":"1","key":"10.1016\/S0304-3975(96)00146-6_BIB52","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1007\/BF01932700","article-title":"An algebraic approach to Cichelli's perfect hashing","volume":"29","author":"Gori","year":"1989","journal-title":"BIT"},{"issue":"6","key":"10.1016\/S0304-3975(96)00146-6_BIB53","doi-asserted-by":"crossref","first-page":"322","DOI":"10.1145\/366604.366654","article-title":"The external language KLIPA for the URAL-2 digital computer","volume":"6","author":"Greniewski","year":"1963","journal-title":"Comm. ACM"},{"issue":"1","key":"10.1016\/S0304-3975(96)00146-6_BIB54","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1145\/174666.174667","article-title":"On randomization in sequential and distributed algorithms","volume":"26","author":"Gupta","year":"1994","journal-title":"ACM Comput. Surveys"},{"key":"10.1016\/S0304-3975(96)00146-6_BIB55","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1145\/953055.5899","article-title":"Finding minimal perfect hash functions","volume":"18","author":"Haggard","year":"1986","journal-title":"ACM SIGCSE Bull."},{"key":"10.1016\/S0304-3975(96)00146-6_BIB56","series-title":"Algorithmics: The Spirit of Computing","author":"Harel","year":"1987"},{"key":"10.1016\/S0304-3975(96)00146-6_BIB57_1","first-page":"81","article-title":"Graph theoretic obstacles to perfect hashing","volume":"98","author":"Havas","year":"1993","journal-title":"Congressus Numerantium"},{"key":"10.1016\/S0304-3975(96)00146-6_BIB57_2","unstructured":"see also Proc. 24th Southeastern Internat. Conf. on Combinatorics, Graph Theory and Computing."},{"key":"10.1016\/S0304-3975(96)00146-6_BIB58","series-title":"Proc. 19th Internat. Workshop on Graph-Theoretic Concepts in Computer Science (WG'93)","first-page":"153","article-title":"Graphs, hypergraphs and hashing","volume":"Vol. 790","author":"Havas","year":"1994"},{"key":"10.1016\/S0304-3975(96)00146-6_BIB59","series-title":"An Introduction to Number Theory","author":"Hua","year":"1975"},{"key":"10.1016\/S0304-3975(96)00146-6_BIB60","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/0020-0190(86)90041-4","article-title":"Two results on tables","volume":"22","author":"Jacobs","year":"1986","journal-title":"Inform. Process. Lett."},{"issue":"12","key":"10.1016\/S0304-3975(96)00146-6_BIB61","doi-asserted-by":"crossref","first-page":"829","DOI":"10.1145\/358800.358806","article-title":"Reciprocal hashing: A method for generating minimal perfect hashing functions","volume":"24","author":"Jaeschke","year":"1981","journal-title":"Comm. ACM"},{"issue":"12","key":"10.1016\/S0304-3975(96)00146-6_BIB62","doi-asserted-by":"crossref","first-page":"728","DOI":"10.1145\/359038.3084011","article-title":"On Cichelli's minimal perfect hash functions method","volume":"23","author":"Jaeschke","year":"1980","journal-title":"Comm. ACM"},{"issue":"3","key":"10.1016\/S0304-3975(96)00146-6_BIB63","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1080\/02533839.1988.9677067","article-title":"Addressing for letter-oriented keys","volume":"11","author":"Jan","year":"1988","journal-title":"J. Chinese Inst. Eng."},{"key":"10.1016\/S0304-3975(96)00146-6_BIB64","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1002\/rsa.3240040303","article-title":"The birth of the giant component","volume":"4","author":"Janson","year":"1993","journal-title":"Random Struct. Algorithms"},{"key":"10.1016\/S0304-3975(96)00146-6_BIB65","series-title":"Fundamental Algorithms, Vol. 1: The Art of Computer Programming","author":"Knuth","year":"1973"},{"key":"10.1016\/S0304-3975(96)00146-6_BIB66","series-title":"Sorting and Searching, Vol. 3: The Art of Computer Programming","author":"Knuth","year":"1973"},{"key":"10.1016\/S0304-3975(96)00146-6_BIB67","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1016\/0304-3975(78)90009-9","article-title":"The expected linearity of a simple equivalence algorithm","volume":"6","author":"Knuth","year":"1978","journal-title":"Theoret. Comput. sci."},{"key":"10.1016\/S0304-3975(96)00146-6_BIB68","series-title":"Proc. ACM SIGMOD","first-page":"190","article-title":"External perfect hashing","author":"Larson","year":"1985"},{"key":"10.1016\/S0304-3975(96)00146-6_BIB69","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1109\/2.7056","article-title":"Hashing for dynamic and static internal tables","volume":"21","author":"Lewis","year":"1988","journal-title":"Computer"},{"issue":"3","key":"10.1016\/S0304-3975(96)00146-6_BIB70","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1007\/BF01190898","article-title":"Clocked adversaries for hashing","volume":"9","author":"Lipton","year":"1993","journal-title":"Algorithmica"},{"key":"10.1016\/S0304-3975(96)00146-6_BIB71","series-title":"Elementary Introduction to Number Theory","author":"Long","year":"1965"},{"key":"10.1016\/S0304-3975(96)00146-6_BIB72","series-title":"Proc. 24th Ann. Symp. on Foundations of Computer Science \u2014 FOCS'83","first-page":"40","article-title":"The program complexity of searching a table","author":"Mairson","year":"1983"},{"key":"10.1016\/S0304-3975(96)00146-6_BIB73","article-title":"Minimal perfect hash functions","author":"Majewski","year":"1992"},{"key":"10.1016\/S0304-3975(96)00146-6_BIB74","series-title":"Data Structures and Algorithms 1: Sorting and Searching","author":"Mehlhorn","year":"1984"},{"issue":"5","key":"10.1016\/S0304-3975(96)00146-6_BIB75","doi-asserted-by":"crossref","first-page":"902","DOI":"10.1137\/0219062","article-title":"On the complexity of a game related to the dictionary problem","volume":"19","author":"Mehlhorn","year":"1990","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0304-3975(96)00146-6_BIB76","series-title":"Proc. 15th Symp. on Mathematical Foundations of Computer Science \u2014 MFCS'90","first-page":"76","article-title":"Dynamic hashing strategies","author":"Meyer auf der Heide","year":"1990"},{"key":"10.1016\/S0304-3975(96)00146-6_BIB77","series-title":"Graphical Evolution: An Introduction to the Theory of Random Graphs","author":"Palmer","year":"1985"},{"issue":"6","key":"10.1016\/S0304-3975(96)00146-6_BIB78","doi-asserted-by":"crossref","first-page":"677","DOI":"10.1145\/78973.78978","article-title":"Fast hashing of variable-length text strings","volume":"33","author":"Pearson","year":"1990","journal-title":"Comm. ACM"},{"key":"10.1016\/S0304-3975(96)00146-6_BIB79","unstructured":"B. Pittel, J. Spencer and N.C. Wormald, The sudden emergence of a giant k-core in a random graph, J. Combin. Theory, Ser. B, submitted."},{"key":"10.1016\/S0304-3975(96)00146-6_BIB80","series-title":"Algorithms and Complexity: Recent Results and New Directions","first-page":"21","article-title":"Probabilistic algorithms","author":"Rabin","year":"1976"},{"key":"10.1016\/S0304-3975(96)00146-6_BIB81","author":"Raghavan","year":"1990"},{"issue":"2","key":"10.1016\/S0304-3975(96)00146-6_BIB82","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1145\/63500.63521","article-title":"File organization using composite perfect hashing","volume":"14","author":"Ramakrishna","year":"1989","journal-title":"ACM Trans. Database Systems"},{"key":"10.1016\/S0304-3975(96)00146-6_BIB83","doi-asserted-by":"crossref","first-page":"482","DOI":"10.4153\/CJM-1962-039-0","article-title":"Euler graphs on labelled nodes","volume":"14","author":"Read","year":"1962","journal-title":"Canad. J. Math."},{"key":"10.1016\/S0304-3975(96)00146-6_BIB84","article-title":"A new method for generating minimal perfect hash functions","author":"Sager","year":"1984"},{"issue":"5","key":"10.1016\/S0304-3975(96)00146-6_BIB85","doi-asserted-by":"crossref","first-page":"523","DOI":"10.1145\/3532.3538","article-title":"A polynomial time generator for minimal perfect hash functions","volume":"28","author":"Sager","year":"1985","journal-title":"Comm. ACM"},{"key":"10.1016\/S0304-3975(96)00146-6_BIB86","series-title":"Proc. 22nd Ann. ACM Symp. on Theory of Computing \u2014 STOC'90","first-page":"224","article-title":"The analysis of closed hashing under limited randomness","author":"Schmidt","year":"1990"},{"issue":"5","key":"10.1016\/S0304-3975(96)00146-6_BIB87","doi-asserted-by":"crossref","first-page":"775","DOI":"10.1137\/0219054","article-title":"The spatial complexity of oblivious k-probe hash functions","volume":"19","author":"Schmidt","year":"1990","journal-title":"SIAM J. Comput."},{"issue":"4","key":"10.1016\/S0304-3975(96)00146-6_BIB88","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1145\/148080.148082","article-title":"Randomized algorithms in \u201cprimitive cultures\u201d","volume":"23","author":"Shallit","year":"1992","journal-title":"SIGACT News"},{"key":"10.1016\/S0304-3975(96)00146-6_BIB89","series-title":"Proc. 30th Ann. Symp. on Foundations of Computer Science \u2014 FOCS'89","first-page":"20","article-title":"On universal classes of fast high performance hash functions, their time-space trade-off, and their applications","author":"Siegel","year":"1989"},{"key":"10.1016\/S0304-3975(96)00146-6_BIB90","series-title":"A selection of Problems in the Theory of Numbers","author":"Sierpinski","year":"1964"},{"key":"10.1016\/S0304-3975(96)00146-6_BIB91","series-title":"Introduction to Data Structures","author":"Singh","year":"1985"},{"key":"10.1016\/S0304-3975(96)00146-6_BIB92","series-title":"Proc. 16th Ann. ACM Symp. on Theory of Computing \u2014 STOC'84","first-page":"391","article-title":"On tape versus core; an application of space efficient perfect hash functions to the invariance of space","author":"Slot","year":"1984"},{"issue":"11","key":"10.1016\/S0304-3975(96)00146-6_BIB93","doi-asserted-by":"crossref","first-page":"841","DOI":"10.1145\/359863.359887","article-title":"Perfect hashing functions: a single probe retrieving method for static sets","volume":"20","author":"Sprugnoli","year":"1977","journal-title":"Comm. ACM"},{"key":"10.1016\/S0304-3975(96)00146-6_BIB94","series-title":"Data Structures Techniques","author":"Standish","year":"1980"},{"key":"10.1016\/S0304-3975(96)00146-6_BIB95","series-title":"Sparse Matrix Computations","first-page":"3","article-title":"Graph theory and gaussian elimination","author":"Tarjan","year":"1976"},{"issue":"2","key":"10.1016\/S0304-3975(96)00146-6_BIB96","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1145\/62.2160","article-title":"Worst-case analysis of set union algorithms","volume":"31","author":"Tarjan","year":"1984","journal-title":"J. ACM"},{"issue":"11","key":"10.1016\/S0304-3975(96)00146-6_BIB97","doi-asserted-by":"crossref","first-page":"606","DOI":"10.1145\/359168.359175","article-title":"Storing a sparse table","volume":"22","author":"Tarjan","year":"1979","journal-title":"Comm. ACM"},{"issue":"3","key":"10.1016\/S0304-3975(96)00146-6_BIB98","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1145\/142040.142077","article-title":"An undergraduate project to compute minimal perfect hashing functions","volume":"24","author":"Trono","year":"1992","journal-title":"SIGCSE Bull."},{"key":"10.1016\/S0304-3975(96)00146-6_BIB99","series-title":"Internat. Conf. on Computing and Information \u2014 ICCI'90","first-page":"275","article-title":"Minimal perfect hashing for large sets of data","author":"Winters","year":"1990"},{"issue":"2","key":"10.1016\/S0304-3975(96)00146-6_BIB100","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1007\/BF02017345","article-title":"Minimal perfect hashing in polynomial time","volume":"30","author":"Winters","year":"1990","journal-title":"BIT"},{"key":"10.1016\/S0304-3975(96)00146-6_BIB101","series-title":"Managing Gigabytes: Compressing and Indexing Documents and Images","author":"Witten","year":"1994"},{"issue":"1","key":"10.1016\/S0304-3975(96)00146-6_BIB102","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1007\/BF01934995","article-title":"A backtracking method for constructing perfect hash functions from a set of mapping functions","volume":"25","author":"Yang","year":"1985","journal-title":"BIT"},{"key":"10.1016\/S0304-3975(96)00146-6_BIB103","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1137\/0214010","article-title":"On the expected performance of path compression algorithms","volume":"14","author":"Yao","year":"1985","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0304-3975(96)00146-6_BIB104","series-title":"Smaller faster table driven parser","author":"Ziegler","year":"1977"}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397596001466?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397596001466?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2021,5,6]],"date-time":"2021-05-06T13:38:32Z","timestamp":1620308312000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0304397596001466"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,8]]},"references-count":108,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[1997,8]]}},"alternative-id":["S0304397596001466"],"URL":"https:\/\/doi.org\/10.1016\/s0304-3975(96)00146-6","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[1997,8]]}}}