Hash Tables — Jump Straight to a Key
A phone's contacts app finds "Priya" instantly among thousands of names. Scanning every contact would be slow, and keeping them sorted still needs a search. A hash table does better: it computes where Priya must be and looks only there. Python's dict, JavaScript's Map and Java's HashMap all work this way.
The rule
Hash the key, take it mod the bucket count, look in one bucket.
A hash table is an array of buckets plus a hash function: a function that turns any key into a whole number.
- Hash the key:
hash("priya")might give 2817. - Reduce it to a bucket index with the remainder: with 8 buckets, 2817 mod 8 = 1.
- Store or look up in bucket 1 only.
Because a lookup repeats exactly the same calculation, it lands in the same bucket the value was stored in. That is why the golden rule of hashing is: equal keys must always produce equal hashes.
Sometimes two different keys land in the same bucket. That is a collision, and it is normal. A common fix, chaining, lets each bucket hold a small list of entries; the table compares keys inside that list to find the right one.
bucket 0: (empty)
bucket 1: ("priya", 555-0101)
bucket 2: ("arun", 555-0142) -> ("meera", 555-0199) <- a collision
bucket 3: (empty)When buckets start to fill up, the table grows (often doubling its bucket count) and re-places every entry, which keeps the chains short.
The shortcut
For any key, run the two-number routine in your head: hash, then remainder. Keys with the same remainder share a bucket.
Reduce the first key
43 mod 10 = 3, so the first entry goes into bucket 3.
The trap: believing hash tables are always one step. On average they are, because good hash functions spread keys out. If many keys collide into the same bucket, a lookup becomes a walk along a long chain.
Drills
Answer fast — trust the rule.
A table has 10 buckets and uses hash mod 10. Which bucket does a key with hash 43 go to?
With 8 buckets, which of these hashes collides with hash 43?
Why must two equal keys always produce the same hash?
When does a hash table lookup become slow?
Remember
- Hash the key, take the remainder by the bucket count, look in one bucket.
- Equal keys must give equal hashes; different keys may still collide.
- The trap: fast on average, slow when collisions pile keys into one bucket.