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 30 September 2013.
HTML page formatted Mon Feb 2 13:10:40 2015.

Cite this as:
Paul E. Black, "perfect hashing", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 30 September 2013. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/perfecthash.html