P-4.4 Hash Tables
You can explain how hashing turns a key into a position, describe two collision strategies, and say what makes lookups constant time on average and linear in the worst case.
The hash table is the workhorse of practical programming, and the dictionary or map in your favourite language almost certainly is one. Its guarantee is average-case rather than worst-case, and that distinction is not academic: a badly distributed hash function degrades it to a list. The related trap is using a mutable value as a key, because changing it after insertion moves where it should have been stored without moving it.
Work through these
A hash function turns a key into a position in a table
Hashing computes a number from the key and reduces it into the range of the table, so a lookup goes straight to one place instead of searching. Good distribution across positions is what makes it work.
NPTEL: Data Structures and Algorithms · CourseCollisions are inevitable, and there are two standard answers
More possible keys than positions guarantees that two will land together. Either each position holds a small list, or the table probes onward for the next free slot.
Load factor and resizing
As a table fills, collisions rise and performance falls, so implementations grow and rehash everything past a threshold. This is the same doubling argument met with growable arrays.
Constant time on average, linear in the worst case
If every key hashed to one position the structure would be a list with extra steps. Adversarial input can force exactly that, which is why some systems randomise their hash function at startup.
Never use something you will modify as a key
The position was computed from the key at insertion, so changing the key afterwards leaves the entry stored where it can no longer be found. Languages with immutable keys are preventing precisely this.
Sign in to keep your progress.
Free resources
We haven't checked most of these for screen reader use yet.
Links last checked 31 Aug 2026.
Stuck here?
Ask a mentor. A real person answers, and they can see exactly which topic you're on. Usually within a couple of working days.
Checking your session…
Topics shown in module order.