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 (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). Austin Appleby's fast MurmurHash (C), including avalanche diagrams for Hsieh SuperFastHash, Jenkin's lookup3, Murmur, Bernstein, FNV, and modified FNV. Overview of different kinds of hash functions. Bret Mulvey's great tutorial on good hash functions, including analysis of and code for FNV, Jenkin's hashes, SHA-1, and other hash and evaluation functions (C#). Herbert Glarner's HSH 11/13 algorithm (Linoleum), including very thorough justification. 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) and (C and Perl).

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

Entry modified 4 February 2009.
HTML page formatted Wed Feb 4 11:08:37 2009.