hash function

(algorithm)

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

Implementation

See the implementations at minimal perfect hashing and Pearson's hash. Bob Jenkins' fast, parameterizable, broadly applicable hash function (C) including code for and evaluations of many other hash functions. 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. Gonnet and Baeza-Yates's 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.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 20 July 2015.
HTML page formatted Mon Jul 20 14:31:11 2015.

Cite this as:
Paul E. Black, "hash function", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 20 July 2015. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/hash.html