How does a program find one username among millions in a fraction of a millisecond, or check that a downloaded file has not been tampered with? The answer is a hash function: a rule that turns any piece of data into a short, fixed-size number. Behind this simple idea lie modular arithmetic, probability and some careful design choices, all of which you can understand with school-level mathematics.
What Is a Hash Function?
A hash function \(h\) maps a key \(k\) (a number, a word, a file) to a value \(h(k)\) in a fixed range, such as \(\{0, 1, \dots, m - 1\}\). A good hash function should be:
- Deterministic: the same key always gives the same hash.
- Fast to compute.
- Uniform: keys should spread evenly across the range, so no position gets overloaded.
Because there are usually far more possible keys than hash values, two different keys will sometimes share a hash. This is called a collision. By the pigeonhole principle, collisions are unavoidable: if you put \(m + 1\) keys into \(m\) slots, at least one slot must hold two keys. Good hashing is not about eliminating collisions but about making them rare and handling them well.
Hash Tables: Searching in Constant Time
A hash table is an array of \(m\) slots. To store a key, compute \(h(k)\) and put the key in that slot. To find it later, compute \(h(k)\) again and look there directly. With a good hash function, searching, inserting and deleting take \(O(1)\) time on average, compared with \(O(\log n)\) for binary search or \(O(n)\) for scanning a list.
The division method
The simplest hash for integer keys is
$$ h(k) = k \bmod m $$
The choice of \(m\) matters. If \(m = 100\), the hash depends only on the last two digits of the key, so keys like 1200, 3400 and 5600 all collide. Choosing \(m\) to be a prime not close to a power of 2 or 10 makes the hash depend on every digit of the key and spreads typical data much more evenly.
Worked Example 1: Hashing with Linear Probing
Insert the keys 12, 44, 13, 88, 23 and 94 into a table of size \(m = 11\), using \(h(k) = k \bmod 11\). Resolve collisions by linear probing: if a slot is full, try the next one, wrapping around at the end.
Step 1: Compute each hash.
- \(12 \bmod 11 = 1\)
- \(44 \bmod 11 = 0\)
- \(13 \bmod 11 = 2\)
- \(88 \bmod 11 = 0\)
- \(23 \bmod 11 = 1\)
- \(94 \bmod 11 = 6\), since \(8 \times 11 = 88\)
Step 2: Insert in order.
- 12 goes to slot 1.
- 44 goes to slot 0.
- 13 goes to slot 2.
- 88 hashes to 0, which is full. Try 1 (full), 2 (full), 3 (empty). Store 88 in slot 3.
- 23 hashes to 1, which is full. Try 2 (full), 3 (full), 4 (empty). Store 23 in slot 4.
- 94 goes to slot 6.
Step 3: Count probes for searching. Finding 88 now takes 4 probes and 23 takes 4 probes, while the others take 1. The average successful search costs
$$ \frac{1 + 1 + 1 + 4 + 4 + 1}{6} = \frac{12}{6} = 2 \text{ probes} $$
Interpretation: the keys formed a cluster in slots 0 to 4. This primary clustering is the main weakness of linear probing. Alternatives include chaining (each slot holds a linked list) and double hashing (the step size comes from a second hash function).
The load factor
The load factor is \(\alpha = \frac{n}{m}\), the number of stored keys divided by the number of slots. Here \(\alpha = \frac{6}{11} \approx 0.55\). With chaining, an unsuccessful search examines \(\alpha\) keys on average, so keeping \(\alpha\) bounded keeps searches \(O(1)\). Real hash tables resize and rehash when \(\alpha\) passes a threshold, often 0.75.
Hashing Strings: Polynomial Hashes
Text must first be turned into a number. A popular method treats the characters as digits in a large base \(B\):
$$ h(s) = \left(s_0 B^{L-1} + s_1 B^{L-2} + \dots + s_{L-1}\right) \bmod M $$
where \(s_i\) are character codes, \(L\) is the length, and \(M\) is a large prime. Using powers of \(B\) means that the order of characters matters, so anagrams get different hashes.
Worked Example 2: Hashing a Word
Compute the hash of "cat" with \(B = 31\) and \(M = 1{,}000{,}000{,}009\). The ASCII codes are c = 99, a = 97, t = 116.
Step 1: Expand the polynomial.
$$ h(\text{cat}) = 99 \times 31^2 + 97 \times 31 + 116 $$
Step 2: Evaluate each term. \(31^2 = 961\), so
- \(99 \times 961 = 95{,}139\)
- \(97 \times 31 = 3{,}007\)
- \(116\)
Step 3: Add: \(95{,}139 + 3{,}007 + 116 = 98{,}262\). This is less than \(M\), so \(h(\text{cat}) = 98{,}262\).
Comparison: the anagram "act" gives \(97 \times 961 + 99 \times 31 + 116 = 93{,}217 + 3{,}069 + 116 = 96{,}402\), a different value. A simple sum of character codes would have given 312 for both words, causing a collision.
In code, this is computed efficiently with Horner's rule: start with \(h = 0\), and for each character set \(h = (h \cdot B + s_i) \bmod M\). That needs only one multiplication per character and keeps every number small.
The Birthday Paradox: How Soon Do Collisions Appear?
In a room of just 23 people, the chance that two share a birthday is about 50.7%. The probability that all \(n\) people have different birthdays is
$$ P(\text{no match}) = \frac{365}{365} \cdot \frac{364}{365} \cdots \frac{365 - n + 1}{365} $$
For \(n = 23\) this is about 0.493, so the chance of a match is \(1 - 0.493 = 0.507\).
The same maths applies to hashing \(n\) keys into \(m\) equally likely values. A good approximation is
$$ P(\text{collision}) \approx 1 - e^{-n^2/(2m)} $$
and a collision becomes more likely than not once \(n \approx 1.18\sqrt{m}\).
Small calculation: with a 32-bit hash, \(m = 2^{32} \approx 4.29 \times 10^9\). Then \(1.18\sqrt{2^{32}} = 1.18 \times 65{,}536 \approx 77{,}000\). So after only about 77,000 items, out of over four billion possible hash values, a collision is already a coin flip. For 100,000 items, \(\frac{n^2}{2m} = \frac{10^{10}}{8.59 \times 10^9} \approx 1.16\), giving \(P \approx 1 - e^{-1.16} \approx 0.69\).
Cryptographic Hash Functions
Hash functions like SHA-256 have stronger requirements than table hashing:
- Pre-image resistance: given a hash, you cannot find an input that produces it.
- Collision resistance: you cannot find any two inputs with the same hash.
- Avalanche effect: changing one bit of input changes about half the output bits.
SHA-256 outputs 256 bits, so by the birthday bound an attacker needs about \(\sqrt{2^{256}} = 2^{128}\) attempts to find a collision, far beyond any computer. These hashes protect stored passwords, verify file downloads, sign documents digitally and link blocks in blockchains.
Did You Know?
- Hans Peter Luhn at IBM described hashing for fast lookup in an internal memo in 1953.
- The older hash function MD5 is now considered broken: researchers produced practical collisions in 2004.
- Websites should never store your actual password, only a salted hash of it, so a stolen database does not directly reveal passwords.
Key Takeaways
- A hash function maps keys to a fixed range; collisions are unavoidable by the pigeonhole principle.
- The division method \(k \bmod m\) works best when \(m\) is a well-chosen prime.
- Polynomial hashes with Horner's rule turn strings into numbers while respecting character order.
- The birthday paradox shows collisions appear after roughly \(\sqrt{m}\) keys.
- Cryptographic hashes like SHA-256 add strong security guarantees for passwords and data integrity.
Working on a data structures or cryptography assignment involving hashing? Amathify's experts and PhD scholars can give you step-by-step solutions via WhatsApp or the Ask a Question form.
Stuck on a problem or assignment?
Our experts and PhD scholars solve maths, physics and chemistry — step by step.