hash function
A function that turns data of any size into a fixed-size value, called its hash, used to find items quickly in a table or to detect any change in the data.
In more detail
A hash function must be deterministic (same input, same output), produce output of a fixed width however large the input, and scatter similar inputs across different values. Hash tables reduce the hash to a slot number to jump straight to a key. Cryptographic hashes such as SHA-256 add a further promise: it is infeasible to find two inputs with the same hash, so they serve as tamper-evident fingerprints.
Examples
hash(42) == 42 # small integers hash to themselves in CPythonhash('apple') # differs on every interpreter launchRelated terms
- hash table — A data structure that stores key-value pairs in an array and uses a hash of each key to jump almost directly to its slot.
- collision — Two different keys producing the same hash, or the same slot in a hash table.
- SHA-256 — A widely used hash function that turns any data into a 256-bit fingerprint, shown as 64 hexadecimal characters.
- deterministic — Always producing the same result from the same inputs, with nothing left to chance or timing.
- hash randomisation — Mixing a secret random value, chosen when a process starts, into string hashing so that hash values cannot be predicted from outside.
Taught in
- What A Hash Function Promises — Algorithms & Data Structures for Working Engineers
- Hash Tables: Chaining, Open Addressing And Load Factor — Algorithms & Data Structures for Working Engineers
- Python Dicts And Sets Under The Hood — Algorithms & Data Structures for Working Engineers
- Collisions In Practice And Hash Flooding — Algorithms & Data Structures for Working Engineers
- Bloom Filters: Membership Without The Data — Algorithms & Data Structures for Working Engineers
- Searching With Hashes Versus Trees — Algorithms & Data Structures for Working Engineers