(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.
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://citeseer.ist.psu.edu/czech92optimal.html. "It uses expected linear time and ... runs very fast in practice." This is a Las Vegas algorithm.
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 17 July 2006.
HTML page formatted Mon Apr 23 13:43:17 2007.
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. 17 July 2006. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/orderPreservMinPerfectHash.html
