minimal perfect hashing

(algorithm)

Definition: A perfect hashing function that maps each different key to a distinct integer and has the same number of possible integers as keys.

Formal Definition: A function f is a minimal perfect hash function for a set of keys K iff ∀ j, k ∈ K f(j) = f(k) → j = k and the range of f(k) is 1... |K|.

Generalization (I am a kind of ...)
perfect hashing, hash function.

Specialization (... is a kind of me.)
order preserving minimal perfect hashing.

Note: After BJ.

Author: PEB

Implementation

Description and code for minimal perfect hashing (C), mph: minimal perfect hash function generator (C). gperf: a near-minimal perfect hashing (C++), click on GNU mirror, click on a nearby server, then gperf.

More information

Edward A. Fox, Lenwood S. Heath, Qi Fan Chen and Amjad M. Daoud, Practical minimal perfect hash functions for large databases, CACM, 35(1):105-121, January 1992.
GPERF: A Perfect Hash Function Generator PDF document.

Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.

Entry modified 14 August 2008.
HTML page formatted Thu Aug 14 12:18:08 2008.

Cite this as:
Paul E. Black, "minimal perfect hashing", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 14 August 2008. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/minimalPerfectHash.html