NIST

hash function

(algorithm)

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

Also known as hash.

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, Merkle tree, 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.

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

Entry modified 15 December 2017.
HTML page formatted Tue Jan 16 10:34:44 2018.

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