The big idea: A hash table does not search. One calculation finds the bucket, which is why lookup is O(1) on average.
How a key finds its bucket
Hash the key
Run the key through a hash function to get a number.
Take the modulo
Take that number modulo the table size.
Go straight there
Go straight to that bucket. No search needed.
One calculation instead of a search.
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 exam-style 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 |
Load factor, and the classes you use
| Idea | What it means |
|---|---|
| Load factor | Items stored ÷ number of buckets. 600 items in 1,000 buckets = 0.6 |
| Why it matters | As it rises, collisions rise and lookups slow down; when it passes a limit (Java's default is 0.75) the table is made bigger and every key is re-hashed into the new buckets |
| Java | HashMap stores key-value pairs; HashSet stores unique values only. Both are hash tables underneath |
| Python | dict stores key-value pairs; set stores unique values only. Both are hash tables underneath |
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 answer broken into clear points, with guidance on how each point earns marks.