A family of perfect hashing methods

Bohdan S. Majewski, Nicholas C. Wormald, George Havas, Zbigniew J. Czech

Research output: Contribution to journalArticleResearchpeer-review

30 Citations (Scopus)

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.

Original languageEnglish
JournalComputer Journal
Volume39
Issue number6
Publication statusPublished - 1996
Externally publishedYes

Cite this

Majewski, B. S., Wormald, N. C., Havas, G., & Czech, Z. J. (1996). A family of perfect hashing methods. Computer Journal, 39(6).