The hostel room number that needs no directory
A BST finds a value in log n steps by comparing. A hash table skips comparing entirely — it computes exactly where a value lives, in one step, almost always.
After this lesson
You should be able to
- Explain what a hash function computes and why.
- Explain why hash table lookup is faster on average than a BST's.
- Explain why two different keys can land in the same slot.
Room number equals roll number, by formula
Imagine a hostel that assigns rooms by a formula: your room number is your roll number modulo the number of rooms. No warden needs to look anything up — anyone can compute your room the instant they know your roll number. Compare this to Unit II's BST, where finding your room means walking down a tree comparing your roll number at every step.
A hash function is exactly that formula: it takes a key and computes an index directly, with no comparisons and no walking. A hash table is simply an array indexed by the output of that formula instead of by a plain sequential position.
int index = roll_number % NUM_ROOMS;
/* No search. No comparison. One arithmetic operation
tells you exactly where to look. */Why this beats a BST on average
Unit II Lesson 4's BST search costs comparisons proportional to the tree's height — about log n even when balanced. A hash table's lookup cost does not depend on how many keys are stored at all, in the ideal case — computing the formula and reading one array slot is the same one step whether the table holds ten keys or ten million.
This is called average-case constant time, written O(1) — not because nothing can ever go wrong, but because under reasonable conditions the cost does not grow with the number of stored keys. The next lesson's worst case is what keeps this from being unconditionally true.
When two roll numbers land in the same room
Two different roll numbers can produce the same remainder when divided by the room count — 105 and 205 both give room 5 in a 100-room hostel. A hash function maps a much larger space of possible keys onto a much smaller table, so by simple counting, some two keys are guaranteed to collide once you have enough of them.
This is called a collision, and it is not a bug or a sign of a bad hash function — it is mathematically unavoidable once the key space exceeds the table size, which it almost always does. What to do when it happens is Lessons 3 and 4.
Try it yourself
A hostel has 50 rooms and uses roll_number % 50 as its hash function. Compute the room for roll numbers 23, 73, 123, and 45, and identify any collisions.
Need a hint?
23, 73, and 123 all differ by exactly 50.
Check the worked solution
23 % 50 = 23, 73 % 50 = 23, 123 % 50 = 23 — all three collide in room 23, because each differs from the last by exactly 50, the table size, and the remainder repeats every multiple of the table size. 45 % 50 = 45, no collision. This is not a coincidence specific to this example — any set of keys spaced exactly one table-width apart will always collide under the division method, which is worth remembering before choosing a table size.
Quick check
Why is a hash table's average lookup cost independent of the number of stored keys, unlike a BST's?
Why this lesson exists
Syllabus mapping
Introduction · Hash Tables
Maps to course outcomes CO1, CO2.