perfect hashing

(algorithm)

Definition: A hash function that maps each different key to a distinct integer. Usually all possible keys must be known beforehand. A hash table that uses a perfect hash has no collisions.

Formal Definition: A function f is perfect for a set of keys K iff ∀ j, k ∈ K f(j) = f(k) → j = k.

Also known as optimal hashing.

Specialization (... is a kind of me.)
minimal perfect hashing, order-preserving minimal perfect hashing.

See also Pearson's hash.

Note: After BJ.

Author: PEB

Implementation

See the implementations at minimal perfect hashing and Gonnet and Baeza-Yates's insert (C), search (C) implementations.

More information

Martin Dietzfelbinger, Anna Karlin, Kurt Melhorn, Friedhelm Meyer Auf Der Heide, Hans Rohnert, and Robert E. Tarjan, Dynamic Perfect Hashing: Upper and Lower Bounds, SIAM J. Comput., 23(4):738-761, August 1994.

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 12 February 2019.
HTML page formatted Wed Mar 13 12:42:46 2019.

Cite this as:
Paul E. Black, "perfect hashing", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 12 February 2019. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/perfecthash.html