Editing Hash function (section)

{{Short description|Mapping arbitrary data to fixed-size values}}
{{redirect|hashlink|the Haxe virtual machine|HashLink}}
{{Redirect|Hash code|the programming competition|Hash Code (programming competition)}}
{{about|a computer programming construct|other meanings of "hash" and "hashing"|Hash (disambiguation)}}
{{More citations needed|date=July 2010}}
[[File:Hash table 4 1 1 0 0 1 0 LL.svg|thumb|240px|right|A hash function that maps names to integers from 0 to 15. There is a [[hash collision|collision]] between keys "John Smith" and "Sandra Dee".]]

A '''hash function''' is any [[Function (mathematics)|function]] that can be used to map [[data (computing)|data]] of arbitrary size to fixed-size values, though there are some hash functions that support variable-length output.<ref>{{cite conference |last1=Aggarwal |first1=Kirti |last2=Verma |first2=Harsh K. |date=March 19, 2015 |url=https://ieeexplore.ieee.org/document/7164747 |title=Hash_RC6 — Variable length Hash algorithm using RC6 |doi=10.1109/ICACEA.2015.7164747 |conference=2015 International Conference on Advances in Computer Engineering and Applications (ICACEA) |access-date=January 24, 2023}}</ref> The values returned by a hash function are called ''hash values'', ''hash codes'', (''hash/message'') ''digests'',<ref>
*{{cite web|url=https://csrc.nist.gov/glossary/term/hash_digest|title=hash digest|publisher=[[NIST]] |website=Computer Security Resource Center - Glossary}}
*{{cite web |url=https://csrc.nist.gov/glossary/term/message_digest |title=message digest |publisher=[[NIST]] |website=Computer Security Resource Center - Glossary}}</ref> or simply ''hashes''.  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 [[hash collision|collision]]).<ref name="knuth-1973">{{cite book |last=Knuth |first=Donald E. |author-link=Donald Knuth |date=1973 |title=The Art of Computer Programming, Vol. 3, Sorting and Searching |publisher=[[Addison-Wesley]] |location=Reading, MA., United States|isbn=978-0-201-03803-3|bibcode=1973acp..book.....K }}</ref>{{rp|page=527}}

Hash functions are related to (and often confused with) [[checksums]], [[check digit]]s, [[Fingerprint (computing)|fingerprints]], [[lossy compression]], [[randomization function]]s, [[Error correction code|error-correcting codes]], and [[cipher]]s. 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 function]]s, while [[cryptographic hash function]]s are used in cybersecurity to secure sensitive data such as passwords.