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