Hashing is the process of converting data of any size into a fixed-size numerical value (the hash) using a mathematical function. The same input always produces the same hash, but it is practically impossible to reverse — you cannot reconstruct the original data from the hash alone.
What is a good mental model for hashing?
Imagine a vast library with 10,000 books. A librarian who checks every shelf sequentially to find a book called Oliver Twist could spend hours. Instead, a clever system passes the book title through a formula that produces a shelf number directly — Oliver Twist always maps to shelf 742. The librarian goes straight there. That formula is a hash function, the shelf number is the hash value, and the library system is a hash table. Hashing trades a small upfront computation for dramatically faster lookup.
What is a hash function?
A hash function takes an input (a string, number, file, or any data) and returns a fixed-length output — the hash or digest. The key properties are:
| Property | Meaning |
|---|---|
| Deterministic | Same input always gives the same hash |
| Fixed output size | Regardless of input length, output is always the same size (e.g. 256 bits for SHA-256) |
| Fast to compute | The hash should be calculable quickly |
| Avalanche effect | A tiny change in input produces a completely different hash |
| One-way | It is computationally infeasible to reverse the hash back to the input |
| Collision resistant | Hard to find two different inputs that produce the same hash |
Simple worked example — a modulo hash function:
Suppose we have an array of 10 slots (indices 0–9). The hash function is h(key) = key mod 10.
| Key | Calculation | Slot |
|---|---|---|
| 47 | 47 mod 10 | 7 |
| 23 | 23 mod 10 | 3 |
| 91 | 91 mod 10 | 1 |
| 56 | 56 mod 10 | 6 |
To retrieve key 47, compute 47 mod 10 = 7 → go directly to slot 7. No searching required.
What is a collision and how is it handled?
A collision occurs when two different inputs produce the same hash value. For example, both 47 and 97 hash to slot 7 using mod 10. Collisions are inevitable in any hash function (there are infinite possible inputs but a finite number of hash values).
Common collision handling strategies:
| Strategy | How it works |
|---|---|
| Chaining | Each slot holds a linked list; colliding items are added to the list at that slot |
| Open addressing (linear probing) | If slot H is occupied, try H+1, H+2, … until an empty slot is found |
| Rehashing | Apply a second hash function to find an alternative slot |
Chaining example: Both 47 and 97 hash to slot 7.
Slot 7 → [47] → [97] → NULL
To find 97, compute hash → slot 7 → traverse the list until 97 is found.
How is hashing used to store passwords securely?
Storing passwords in plain text is dangerous — if a database is stolen, every password is immediately compromised. Instead, a website stores the hash of the password:
- User creates password
"MyP@ssw0rd". - Server computes
hash("MyP@ssw0rd")→ stores the hash (e.g.e3b0c44298fc1c...). - At login, user enters
"MyP@ssw0rd". - Server hashes the entry → compares with stored hash.
- If they match → access granted; the original password is never stored.
Even if hackers steal the database, they get only hashes — and because hashing is one-way, they cannot reverse them to find the passwords. Modern systems add a salt (a random value appended to the password before hashing) to prevent attackers using precomputed tables of common password hashes (rainbow tables).
What is the difference between hashing and encryption?
This distinction is crucial and commonly tested at GCSE:
| Feature | Hashing | Encryption |
|---|---|---|
| Reversible? | No — one-way function | Yes — can be decrypted with the key |
| Output size | Fixed, regardless of input | Typically similar to input size |
| Purpose | Integrity checking, password storage | Confidentiality of data in transit/at rest |
| Key required? | No | Yes |
| Example uses | Password verification, checksums, hash tables | HTTPS, file encryption, messaging apps |
Encryption is designed to be reversible by authorised parties; hashing is deliberately irreversible.
How is hashing used to check data integrity?
When you download a file, the website often shows a checksum (a hash of the file). After downloading, your system hashes the file and compares the result. If even one bit of the file changed during download (corruption, tampering), the hash will be completely different — a mismatch flags the problem immediately. This is the avalanche effect in action.
Frequently asked questions
Can two passwords produce the same hash (a collision)?
In theory, yes — any hash function can produce collisions because the output space is finite. However, cryptographic hash functions (SHA-256, bcrypt) are designed so that finding a collision requires astronomical computing time. For practical security purposes, they are treated as collision-free. Older functions like MD5 have known efficient collision attacks and must not be used for security.
What is a rainbow table attack?
A rainbow table is a precomputed list of common passwords and their corresponding hashes. If a stolen database contains hash("password123"), an attacker looks it up in the rainbow table and finds "password123" instantly. Salting defeats this: a unique random salt is concatenated with each password before hashing, so even identical passwords produce different hashes, making rainbow tables useless.
Is SHA-256 a hashing algorithm or an encryption algorithm?
SHA-256 (Secure Hash Algorithm, 256-bit output) is a hashing algorithm — it is one-way and produces a fixed 64-character hexadecimal digest. It is not encryption. SHA-256 is widely used in digital signatures, blockchain (Bitcoin mines by finding inputs that hash to a target with many leading zeros), and TLS certificate verification.
Why do hash tables give O(1) average lookup speed?
In an ideal hash table with no collisions, finding any item takes exactly one computation (the hash function) and one array access — constant time regardless of how many items are stored. This is O(1) in Big-O notation. With collisions handled by chaining, the worst case is O(n) (if all items hash to the same slot and form a long list), but with a good hash function and a table large enough, the average chain length stays close to 1, making real-world performance effectively O(1).
Demystify hashing — from hash tables to password security — with Professor Turing at aitutors.me.