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, HyperLogLog, 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 8 August 2023.
HTML page formatted Wed Aug 9 16:46:43 2023.

Cite this as:
Paul E. Black, "hash function", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 8 August 2023. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/hash.html