The big idea: A hash table does not search. It runs the key through a hash function to get a number, takes that number modulo the table size, and goes straight to that bucket.
One calculation instead of a search — which is why lookup is O(1) on average.
Step through: hashing a key to a bucket, a second key landing elsewhere, a collision, and how chaining resolves it.
Interactive diagram
Explore the labelled diagram, charts and maps for this topic in full study mode.
Free preview
This is the free notes preview
You're reading the free notes. Aimnova Pro unlocks the full study experience — and you can try it with your first topic free to keep:
- FlashcardsLock in vocabulary and key terms with spaced repetition.
- Practice questionsAnswer exam-style questions and get instant AI marking.
- Mock exams & past-paper vaultSit full mocks and see exactly how examiners award marks.
- Personalised study planA daily plan built around your exam date and weak areas.
Three requirements
- Deterministic — the same key must always give the same bucket, or nothing could ever be found again
- Fast — it runs on every single operation, so a slow hash destroys the whole point
- Uniform — keys should spread evenly across buckets, because clustering is what turns O(1) into O(n)
Collisions are certain, not a bug: There are more possible keys than buckets, so two keys must eventually map to the same one. That is arithmetic, not a flaw in the function.
A hash table is judged on how well it handles collisions, not on whether it avoids them.
Practice with real exam questions
Answer exam-style questions and get AI feedback that shows you exactly what examiners want to see in a full-marks response.
| Chaining | Open addressing | |
|---|---|---|
| Colliding keys go | In a list inside the bucket | Into the next free bucket |
| Table can hold | More items than buckets | At most one per bucket |
| Lookup | Find bucket, search the short chain | Probe onwards until found or empty |
| Degrades when | One chain grows long | The table fills up — clusters form |
| Deleting | Straightforward | Needs a marker, or later probes stop early |
Average O(1), worst case O(n): With keys spread evenly, a lookup touches one bucket and a very short chain — O(1).
With a poor hash function that sends every key to the same bucket, the chain is the table and lookup becomes a linear search — O(n). Same structure, same code, completely different performance.
Never write O(1) alone: Write O(1) on average, O(n) in the worst case. The qualification is frequently the mark, because it shows you know the performance depends on the hash function rather than on the structure.
How this is tested — you must explain how an address is computed rather than searched, and why collisions are inevitable. It comes up two ways:
Paper 2 — working with code
- Explain hashing and collision resolution, 4-6 marks
- Compute which bucket a key lands in
- State why a hash function must be deterministic
Paper 2 — the algorithmic-thinking question
- Compare a hash table with a BST for a scenario
- Explain when O(1) stops being true
The classic trap: Saying a hash table is "always O(1)". It is O(1) on average. Everything depends on the hash function spreading keys evenly — and an answer that never mentions the worst case has missed what is being examined.
A dictionary app stores 50,000 words and must look up a definition instantly. Explain how a hash table achieves this, why collisions occur, and when the approach would fail.
Model answer plan
See the mark-by-mark plan — for / against / judgement, with marking guidance — in study mode.