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 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.
Publication Year: 1996
Publication Date: 1996-06-01
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
Cited By Count: 100
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot