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.

See also Pearson's hash.

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 3 February 2009.
HTML page formatted Wed Feb 4 11:02:22 2009.

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. 3 February 2009. (accessed TODAY) Available from: http://www.itl.nist.gov/div897/sqg/dads/HTML/minimalPerfectHash.html