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 28 February 2011.
HTML page formatted Tue Dec 6 16:16:32 2011.

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