hash function


Definition: A function that maps keys to integers, usually to get an even distribution on a smaller set of values.

Specialization (... is a kind of me.)
different kinds: linear hash, perfect hashing, minimal perfect hashing, order-preserving minimal perfect hashing, specific functions: Pearson's hash, multiplication method.

Aggregate parent (I am a part of or used in ...)
hash table, uniform hashing, universal hashing, Bloom filter, locality-sensitive hashing.

See also simple uniform hashing.

Note: The range of integers is typically [0... m-1] where m is a prime number or a power of 2.

Author: PEB


See the implementations at minimal perfect hashing (C++ and C) and Pearson's hash (C). Bob Jenkins' fast, parameterizable, broadly applicable hash function (C) including code for and evaluations of many other hash functions. A review and comparison of many integer hash functions (C). Fowler/Noll/Vo or FNV hash function (C). Arash Partow's implementations of various General Hash Functions (C, C++, Pascal, Object Pascal, Java, Ruby, Python) and Bloom filter for strings. Hash functions for strings (C). Austin Appleby's fast MurmurHash (C), including avalanche diagrams for Hsieh SuperFastHash, Jenkin's lookup3, Murmur, Bernstein, FNV, and modified FNV.

More information

Hashing Functions.

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, "hash function", 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:

to NIST home page