order-preserving minimal perfect hashing

(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

More information

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

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 14 April 2009.
HTML page formatted Mon Feb 2 13:10:40 2015.

Cite this as:
Bob Jenkins, "order-preserving minimal perfect hashing", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 14 April 2009. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/orderPreservMinPerfectHash.html