(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 http://citeseerx.ist.psu.edu/viewdoc/summary?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 E. Black.
Entry modified 14 April 2009.
HTML page formatted Tue Dec 6 16:16:32 2011.
Cite this as:
Bob Jenkins, "order-preserving minimal perfect hashing", in
Dictionary of Algorithms and Data
Structures [online], Paul E. Black, ed.,
U.S. National Institute of
Standards and Technology. 14 April 2009. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/orderPreservMinPerfectHash.html
