order-preserving minimal perfect hashing (original) (raw)

(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 DOI 10.1.1.51.5566. "It uses expected linear time and ... runs very fast in practice."

Go to theDictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 25 July 2022.
HTML page formatted Wed Oct 30 12:15:31 2024.

Cite this as:
Bob Jenkins, "order-preserving minimal perfect hashing", inDictionary 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