(algorithm)
Definition: A minimal perfect hashing function for keys in S such that if k1, k2 ∈ S and k1 > k2, then f(k1) > f(k2).
Generalization (I am a kind of ...)
minimal perfect hashing, linear hash, Las Vegas algorithm.
See also Pearson's hash.
Note: For example, if the keys are stored in order in an array, the array offsets are an order preserving minimal perfect hash of the keys.
Author: BJ
Zbigniew J. Czech, George Havas, and Bohdan S. Majewski, An Optimal Algorithm for Generating Minimal Perfect Hash Functions, Information Processing Letters, 43(5):257-264, October 1992. Available at DOI 10.1.1.51.5566. "It uses expected linear time and ... runs very fast in practice."
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 25 July 2022.
HTML page formatted Mon Jul 25 09:56:30 2022.
Cite this as:
Bob Jenkins, "order-preserving minimal perfect hashing", in
Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 25 July 2022. (accessed TODAY)
Available from: https://www.nist.gov/dads/HTML/orderPreservMinPerfectHash.html