Finding Elvin's number in a phone book by scanning the whole list takes O(n) time; binary search in a sorted list takes O(log n). What if the number of steps did not depend on n at all? That is what a hash table does: it turns the key directly into an array index. Python's dict and set, database hash indexes, caches and compilers' symbol tables are all built on this idea.
The hash function
Hash tableDefinition
An array of size m (its cells are called buckets) together with a hash function h that maps a key to an index in 0 … m − 1. A key → value pair is stored in bucket h(key), and a lookup starts right at that bucket.
Where
- s₀ … sₖ₋₁
- numeric codes of the string's characters
- p
- base (usually a small prime such as 31)
- k
- length of the string
- m
- number of buckets
A polynomial hash depends on both the characters and their order: “ab” and “ba” get different hashes.
Example 1: hashing a string
Problem
Give letters codes a = 1, b = 2, c = 3. With p = 31 and m = 11, which bucket does the key “cab” go to?
Show solutionHide solution
Solution
2916 = 11 · 265 + 1, so 2916 mod 11 = 1.
“cab” goes to bucket 1. In practice Horner's scheme is used: h = (h · 31 + code) — one multiplication and one addition per character, i.e. O(k).
- Deterministic: the same key always gives the same hash.
- Uniformity: keys spread roughly evenly over the buckets.
- Speed: computing it takes O(key length) time.
- Uses the whole key: a function that looks only at the first letter sends “Aysel” and “Anar” to the same bucket.
Collisions and how to resolve them
There are far more possible keys than buckets, so by the pigeonhole principle two different keys landing in the same bucket — a collision — is unavoidable. It also happens sooner than expected: this is the “birthday paradox”. In a group of just 23 people the chance that two share a birthday is already above 50%.
Where
- k
- number of keys inserted
- m
- number of buckets
m = 365, k = 23: k(k − 1)/2 = 253, 253/365 ≈ 0.693, e^(−0.693) ≈ 0.5. About √m keys are enough for collisions to start.
- Separate chaining: each bucket holds a list, and colliding keys are simply appended to it.
- Open addressing: all keys live in the array itself; if a bucket is taken, we look for the next free slot. Linear probing: h(k), h(k) + 1, h(k) + 2, … (mod m).
- Quadratic probing (h(k) + i²) and double hashing (h₁(k) + i · h₂(k)) reduce the piling-up of keys (clustering).
Example 2: linear probing
Problem
m = 11, h(k) = k mod 11. Insert the keys 12, 44, 13, 88, 23, 94, 11, 39, 20 using linear probing.
Show solutionHide solution
Solution
88 → 0 taken, 1 taken, 2 taken → 3 (4 probes).
23 → 1, 2, 3 taken → 4 (4 probes).
94 → 6.
11 → 0, 1, 2, 3, 4 taken → 5 (6 probes).
39 → 6 taken → 7; 20 → 9.
Result: [44, 12, 13, 88, 23, 11, 94, 39, —, 20, —], α = 9/11 ≈ 0.82.
Cells 0–7 form a cluster: every new key that lands there will travel a long way.
def insert_linear(table, key):
m = len(table)
i = key % m
probes = 1
while table[i] is not None:
i = (i + 1) % m
probes += 1
table[i] = key
return probes
table = [None] * 11
for k in [12, 44, 13, 88, 23, 94, 11, 39, 20]:
p = insert_linear(table, k)
print(k, '-> slot', table.index(k), 'probes:', p)
print(table)
print('load factor:', round(9 / 11, 2))Expected output
12 -> slot 1 probes: 1 44 -> slot 0 probes: 1 13 -> slot 2 probes: 1 88 -> slot 3 probes: 4 23 -> slot 4 probes: 4 94 -> slot 6 probes: 1 11 -> slot 5 probes: 6 39 -> slot 7 probes: 2 20 -> slot 9 probes: 1 [44, 12, 13, 88, 23, 11, 94, 39, None, 20, None] load factor: 0.82
Load factor and O(1) on average
Where
- α
- load factor
- n
- number of keys in the table
- m
- number of buckets
With chaining α is the average chain length and may exceed 1; with open addressing α < 1 always.
Where
- E
- expected number of probes in an unsuccessful search (key absent)
Assuming a uniformly spreading hash. The linear-probing formula comes from Knuth's analysis; as α → 1 the probes explode.
| α | Chaining: 1 + α | Linear probing (unsuccessful) | Linear probing (successful) ½(1 + 1/(1 − α)) |
|---|---|---|---|
| 0.5 | 1.5 | 2.5 | 1.5 |
| 0.75 | 1.75 | 8.5 | 2.5 |
| 0.9 | 1.9 | 50.5 | 5.5 |
When α crosses a threshold (0.75 in Java's HashMap, for example), the table roughly doubles and every key is hashed again for the new m (rehashing). This occasional O(n) work is amortised exactly as in a dynamic array, so insert, search and delete stay O(1) on average. In the worst case — all keys in one bucket — they are O(n).
class HashMap:
def __init__(self, m=5):
self.buckets, self.n = [[] for _ in range(m)], 0
def _index(self, key):
h = 0
for ch in key:
h = h * 31 + ord(ch)
return h % len(self.buckets)
def put(self, key, value):
bucket = self.buckets[self._index(key)]
for pair in bucket:
if pair[0] == key:
pair[1] = value
return
bucket.append([key, value])
self.n += 1
if self.n / len(self.buckets) > 0.75:
pairs = [p for b in self.buckets for p in b]
self.buckets = [[] for _ in range(2 * len(self.buckets) + 1)]
for p in pairs:
self.buckets[self._index(p[0])].append(p)
def get(self, key):
for k, v in self.buckets[self._index(key)]:
if k == key:
return v
caps = HashMap()
for pair in ['Azerbaijan:Baku', 'Georgia:Tbilisi', 'Japan:Tokyo', 'Italy:Rome', 'Egypt:Cairo']:
caps.put(*pair.split(':'))
print(caps.get('Azerbaijan'), caps.get('Japan'), caps.get('France'))
print(len(caps.buckets), [len(b) for b in caps.buckets])Expected output
Baku Tokyo None 11 [1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0]
None.| Structure | Search | Insert | Order / range query |
|---|---|---|---|
| Unsorted array | O(n) | amortised O(1) | no |
| Sorted array | O(log n) | O(n) | yes |
| Balanced search tree | O(log n) | O(log n) | yes |
| Hash table | O(1) avg, O(n) worst | O(1) avg | no |
Remember
- A hash table maps a key to index h(k) mod m; operations are O(1) on average and O(n) in the worst case.
- Collisions are unavoidable (birthday paradox): they start after about √m keys.
- Chaining keeps lists in the buckets; open addressing probes for the next free cell and marks deleted slots with tombstones.
- Load factor α = n/m; when α passes a threshold the table grows and rehashes (amortised O(1)).
- A hash table keeps no order: choose a tree for range and minimum queries.