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.
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 12 February 2019.
HTML page formatted Tue Feb 12 10:57:42 2019.
Cite this as:
Paul E. Black, "hash function", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 12 February 2019. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/hash.html