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.

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 21 March 2005.
HTML page formatted Mon Sep 11 09:46:06 2006.

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. 21 March 2005. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/perfecthash.html