A FAMILY OF PERFECT HASHING METHODS

Minimal perfect hash functions are used for memory efficient storage a nd fast retrieval of items from static sets. We present an infinite fa mily of efficient and practical algorithms for generating order preser ving minimal perfect hash functions. We show that almost all members o f the family construct space and time optimal order preserving minimal perfect hash functions, and we identify the one with minimum constant s. Members of the family generate a hash function in two steps. First a special kind of function into an r-graph is computed probabilistical ly. Then this function is refined deterministically to a minimal perfe ct hash function. We give strong theoretical evidence that the first s tep uses linear random time. The second step runs in linear determinis tic time. The family not only has theoretical importance, but also off ers the fastest known method for generating perfect hash functions.