Hash function: Difference between revisions

Revision as of 12:33, 27 December 2024

Revision as of 22:40, 16 March 2025

Line 6:

[[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 digests/message'',) ''digests'', or simply ''hashes''.<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 hash|url=https://csrc.nist.gov/glossary/term/message_digest |title=message digest |access-datepublisher=January[[NIST]] 1,|website=Computer 2024Security 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.