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 Black.

Entry modified 9 May 2011.
HTML page formatted Mon Feb 2 13:10:39 2015.

Cite this as:
Paul E. Black, "minimal perfect hashing", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 9 May 2011. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/minimalPerfectHash.html