Hash function

"hashlink" redirects here. For the Haxe virtual machine, see HashLink.
"Hash code" redirects here. For the programming competition, see Hash Code (programming competition).
This article is about a computer programming construct. For other meanings of "hash" and "hashing", see Hash (disambiguation).
A hash function that maps names to integers from 0 to 15. There is a collision between keys "John Smith" and "Sandra Dee".

A hash function is any function that can be used to map data of arbitrary size to fixed-size values, though there are some hash functions that support variable-length output.[1] The values returned by a hash function are called hash values, hash codes, hash digests, digests, or simply hashes.[2] The values are usually used to index a fixed-size table called a hash table. Use of a hash function to index a hash table is called hashing or scatter-storage addressing.

Hash functions and their associated hash tables are used in data storage and retrieval applications to access data in a small and nearly constant time per retrieval. They require an amount of storage space only fractionally greater than the total space required for the data or records themselves. Hashing is a computationally- and storage-space-efficient form of data access that avoids the non-constant access time of ordered and unordered lists and structured trees, and the often-exponential storage requirements of direct access of state spaces of large or variable-length keys.

Use of hash functions relies on statistical properties of key and function interaction: worst-case behavior is intolerably bad but rare, and average-case behavior can be nearly optimal (minimal collision).[3]: 527 

Hash functions are related to (and often confused with) checksums, check digits, fingerprints, lossy compression, randomization functions, error-correcting codes, and ciphers. Although the concepts overlap to some extent, each one has its own uses and requirements and is designed and optimized differently. The hash function differs from these concepts mainly in terms of data integrity. Hash tables may use non-cryptographic hash functions, while cryptographic hash functions are used in cybersecurity to secure sensitive data such as passwords.

  1. ^ Aggarwal, Kirti; Verma, Harsh K. (March 19, 2015). Hash_RC6 — Variable length Hash algorithm using RC6. 2015 International Conference on Advances in Computer Engineering and Applications (ICACEA). doi:10.1109/ICACEA.2015.7164747. Retrieved January 24, 2023.
  2. ^ "NIST Glossary — hash digest". Retrieved January 1, 2024.
  3. ^ Knuth, Donald E. (1973). The Art of Computer Programming, Vol. 3, Sorting and Searching. Reading, MA., United States: Addison-Wesley. Bibcode:1973acp..book.....K. ISBN 978-0-201-03803-3.