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.
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.
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 25 February 2019.
HTML page formatted Wed Mar 13 12:42:46 2019.
Cite this as:
Paul E. Black, "minimal perfect hashing", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 25 February 2019. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/minimalPerfectHash.html