A family of perfect hashing methods


Autoria(s): Majewski, BS; Wormald, NC; Havas, G; Czech, ZJ
Data(s)

01/01/1996

Resumo

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.

Identificador

http://espace.library.uq.edu.au/view/UQ:57372

Idioma(s)

eng

Palavras-Chave #Computer Science, Hardware & Architecture #Computer Science, Information Systems #Computer Science, Software Engineering #Algorithms #Time
Tipo

Journal Article