4.1Hash functions and chaining
The idea
A hash function turns a key into a table index. Different keys can land on the same slot, a collision. Chaining keeps a list in each slot.
Think of it like this: A set of mailboxes labelled by the last digit of a number: several letters can share a box.
Why it exists
Chaining never overflows and is easy to analyse, so exam questions often use it.
How it works
- Compute h(k) = k mod m.
- Insert the key at the slot (head or tail of its chain).
- Search follows the chain.
- The average chain length is the load factor α = n / m.
Worked example: m = 9, keys 5 28 19 15 20 33 12 17 10
Slot 1 gets 28, 19, 10; slot 5 gets 5; slot 6 gets 15, 33; slot 3 gets 12; slot 8 gets 17; slot 2 gets 20. Longest chain: 3.
Now play with it
- →Run the default keys and read the chains.
- →Change m to a power of 2 and see more collisions for patterned keys.
| slot | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| chain |
Green = where the key landed, red = occupied slots probed on the way.
- 5 mod 9 = 5: append to the chain at slot 5
- 28 mod 9 = 1: append to the chain at slot 1
- 19 mod 9 = 1: append to the chain at slot 1
- 15 mod 9 = 6: append to the chain at slot 6
- 20 mod 9 = 2: append to the chain at slot 2
- 33 mod 9 = 6: append to the chain at slot 6
- 12 mod 9 = 3: append to the chain at slot 3
- 17 mod 9 = 8: append to the chain at slot 8
- 10 mod 9 = 1: append to the chain at slot 1
Primary clustering (linear probing) makes runs of filled slots grow; quadratic probing may skip some slots entirely, so it can fail even when the table is not full. Double hashing here uses h2(k) = 5 − (k mod 5).
Check yourself
For m = 10 and keys 12, 22, 32, 42, the longest chain has length
Exam notes (the dense version)
A hash function maps a key to a slot: h(k) = k mod m is the usual choice, with m a prime not close to a power of 2. Two keys in the same slot collide. In separate chaining each slot holds a linked list; the table never overflows. Expected cost of search is 1 + α with load factor α = n/m. Worst case (all keys collide) is O(n).
Previous year questions: Hashing (6)
PYQs are grouped by topic, so this is the full set for Hashing; try the ones that match this subtopic. Open all 6 on the topic page.