© 1996 by British Computer Society
A Family of Perfect Hashing Methods
1 Department of Computer Science and Software Engineering, University of Newcastle, Callaghan NSW 2308, Australia, 2 Department of Mathematics, University of Melbourne, Parkville, Victoria 3052, Australia, 3 Department of Computer Science, The University of Queensland, Queensland 4072, Australia, 4 Institutes of Computer Science, Silesia University of Technology and Polish Academy of Sciences, Gliwice, Poland 44-100.
Minimal perfect hash functions are used for memory efficient storage and fast retrieval of items from static sets. We present an infinite family of efficient and practical algorithms for generating order preserving minimal perfect hash functions. We show that almost all members of the family construct space and time optimal order preserving minimal perfect hash functions, and we identify the one with minimum constants. Members of the family generate a hash function in two steps. First a special kind of function into an r-graph is computed probabilistically. Then this function is refined deterministically to a minimal perfect has function. We give strong theoretical evidence that the first step uses linear random time. The second step runs in linear deterministic time. The family not only has theoretical importance, but also offers the fastest known methods for generating perfect hash functions.
Received February 7, 1995. revised July 4, 1996.
* Department of Computer Science and Software Engineering, University of Newcastle, Callaghan NSW 2308
Department of Mathematics, University of Melbourne, Parkville, Victoria 3052
¶ Department of Computer Science, The University of Queensland, Queensland 4072, Australia
Institutes of Computer Science, Silesia University of Technology and Polish Academy of Sciences, Gliwice, Poland 44-100