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 (C++, C), insert (C), search (C).

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 E. Black.

Entry modified 4 February 2009.
HTML page formatted Wed Feb 4 11:08:37 2009.

Cite this as:
Paul E. Black, "perfect hashing", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 4 February 2009. (accessed TODAY) Available from: http://www.itl.nist.gov/div897/sqg/dads/HTML/perfecthash.html