A family of perfect hashing methods

Majewski, BS, Wormald, NC, Havas, G and Czech, ZJ (1996) A family of perfect hashing methods. Computer Journal, 39 6: 547-554. doi:10.1093/comjnl/39.6.547

Author Majewski, BS
Wormald, NC
Havas, G
Czech, ZJ
Title A family of perfect hashing methods
Journal name Computer Journal   Check publisher's open access policy
ISSN 0010-4620
Publication date 1996
Sub-type Article (original research)
DOI 10.1093/comjnl/39.6.547
Volume 39
Issue 6
Start page 547
End page 554
Total pages 8
Language eng
Abstract 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 hash 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 method for generating perfect hash functions.
Keyword Computer Science, Hardware & Architecture
Computer Science, Information Systems
Computer Science, Software Engineering
Q-Index Code C1
Q-Index Status Provisional Code
Institutional Status Unknown

Document type: Journal Article
Sub-type: Article (original research)
Collection: School of Information Technology and Electrical Engineering Publications
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 23 times in Thomson Reuters Web of Science Article | Citations
Google Scholar Search Google Scholar
Created: Mon, 13 Aug 2007, 16:35:53 EST