Collision Resolution - PCCST303

No hash function can guarantee two different keys never land on the same table index. When h(key1) == h(key2) for two different keys, that is a collision, and it has to be resolved somehow, or the second key would overwrite the first.

Definition

Collision resolution is the strategy used to find a valid slot for a key when its hash-computed slot is already occupied by a different key.

The techniques fall into two families: open addressing (probe for another slot within the same table) and chaining (store colliding keys in a separate list attached to that slot).

Linear probing

Definition

Linear probing resolves a collision at slot h(key) by checking the next slot, h(key)+1, then h(key)+2, and so on (wrapping around to 0 at the end of the table), until an empty slot is found.

LINEAR_PROBE(H, KEY, M)
// H is the initial hash value h(KEY)
// KEY is the key being inserted
// M is the table size
 
1. i = 0
2. While TABLE[(H + i) mod M] is occupied:
       i = i + 1
3. Insert KEY at TABLE[(H + i) mod M]

Example: table size 7, h(key) = key mod 7. Insert 50, 700, 76, 85, 92, 73, 101, in order.

Insert 50. h(50) = 1. Slot 1 is empty, place it there:

Index

0123456

Insert 700. h(700) = 0. Slot 0 is empty, place it there:

Index

700

0123456

Insert 76. h(76) = 6. Slot 6 is empty, place it there:

Index

700

0123456

Insert 85. h(85) = 1. Slot 1 is occupied (by 50), probe slot 2. Slot 2 is empty, place it there:

Index

700

0123456

Insert 92. h(92) = 1. Slot 1 occupied, probe slot 2. Slot 2 occupied, probe slot 3. Slot 3 is empty, place it there:

Index

700

0123456

Insert 73. h(73) = 3. Slot 3 is occupied, probe slot 4. Slot 4 is empty, place it there:

Index

700

0123456

Insert 101. h(101) = 3. Slot 3 occupied, probe slot 4. Slot 4 occupied, probe slot 5. Slot 5 is empty, place it there:

Index

700

101

0123456

Key	h(key)	Probes tried	Slot placed
`50`	1	1	1
`700`	0	0	0
`76`	6	6	6
`85`	1	1, 2	2
`92`	1	1, 2, 3	3
`73`	3	3, 4	4
`101`	3	3, 4, 5	5

Linear probing's weakness is primary clustering: once several keys land near each other, any new key hashing into that stretch has to probe through the whole cluster, making the cluster grow even longer. This progressively slows down insertion and search as the table fills.

Quadratic probing

Definition

Quadratic probing resolves a collision by checking slots h(key)+1², h(key)+2², h(key)+3², ... (mod table size), spreading probes out faster than linear probing's fixed step of 1.

QUADRATIC_PROBE(H, KEY, M)
// H is the initial hash value h(KEY)
// KEY is the key being inserted
// M is the table size
 
1. i = 0
2. While TABLE[(H + i²) mod M] is occupied:
       i = i + 1
3. Insert KEY at TABLE[(H + i²) mod M]

Example: table size 7, same key set as linear probing: 50, 700, 76, 85, 92, 73, 101.

Insert 50. h(50) = 1. Slot 1 is empty, place it there:

Index

0123456

Insert 700. h(700) = 0. Slot 0 is empty, place it there:

Index

700

0123456

Insert 76. h(76) = 6. Slot 6 is empty, place it there:

Index

700

0123456

Insert 85. h(85) = 1. Slot 1 occupied, probe 1 + 1² = 2. Slot 2 is empty, place it there:

Index

700

0123456

Insert 92. h(92) = 1. Slot 1 occupied, probe 1 + 1² = 2. Slot 2 occupied, probe 1 + 2² = 5. Slot 5 is empty, place it there:

Index

700

0123456

Insert 73. h(73) = 3. Slot 3 is empty, place it there:

Index

700

0123456

Insert 101. h(101) = 3. Slot 3 occupied, probe 3 + 1² = 4. Slot 4 is empty, place it there:

Index

700

101

0123456

Key	h(key)	Probes tried	Slot placed
`50`	1	1	1
`700`	0	0	0
`76`	6	6	6
`85`	1	1, 2	2
`92`	1	1, 2, 5	5
`73`	3	3	3
`101`	3	3, 4	4

Notice 92 needed 3 probes under quadratic probing but also 3 under linear probing here, while 101 needed only 2 probes under quadratic versus 3 under linear, since quadratic probing spreads out from the cluster faster once it grows beyond one slot.

Quadratic probing avoids primary clustering (probes spread out quickly), but introduces secondary clustering: keys that collide on the same initial slot always follow the same probe sequence (+1, +4, +9, ...), so they still cluster together, just less severely than linear probing.

Double hashing

Definition

Double hashing uses a second hash function h2(key) to determine the probe step size, so different keys colliding on the same slot follow different probe sequences: h1(key), h1(key)+h2(key), h1(key)+2·h2(key), ... (mod table size).

DOUBLE_HASH_PROBE(H1, H2, KEY, M)
// H1 is the initial hash value h1(KEY)
// H2 is the step size h2(KEY)
// KEY is the key being inserted
// M is the table size
 
1. i = 0
2. While TABLE[(H1 + i * H2) mod M] is occupied:
       i = i + 1
3. Insert KEY at TABLE[(H1 + i * H2) mod M]

A common choice: h1(key) = key mod M, h2(key) = R - (key mod R) for a prime R slightly smaller than M, chosen so h2(key) is never 0 (which would mean no movement at all).

Example: table size 11, h1(key) = key mod 11, h2(key) = 5 - (key mod 5). Insert 27, 43, 683, 72, 39, in order.

Insert 27. h1(27) = 5. Slot 5 is empty, place it there:

Index

012345678910

Insert 43. h1(43) = 10. Slot 10 is empty, place it there:

Index

012345678910

Insert 683. h1(683) = 1. Slot 1 is empty, place it there:

Index

683

012345678910

Insert 72. h1(72) = 6. Slot 6 is empty, place it there:

Index

683

012345678910

Insert 39. h1(39) = 6. Slot 6 is occupied. h2(39) = 5 - (39 mod 5) = 5 - 4 = 1. Probe (6 + 1·1) mod 11 = 7. Slot 7 is empty, place it there:

Index

683

012345678910

Key	h1(key)	h2(key)	Probes tried	Slot placed
`27`	5	—	5	5
`43`	10	—	10	10
`683`	1	—	1	1
`72`	6	—	6	6
`39`	6	1	6, 7	7

Double hashing avoids both primary and secondary clustering, since the probe sequence depends on the key itself (via h2), not just a fixed pattern. This makes it the strongest open-addressing technique among the three, at the cost of computing a second hash function.

Chaining (open hashing)

Definition

Chaining, also called open hashing, resolves collisions by storing every key that hashes to the same slot in a linked list attached to that slot, instead of probing for a different slot in the same table.

Example: table size 5, h(key) = key mod 5. Insert 12, 22, 7, 17, 5, 13, in order.

Insert 12. h(12) = 2. Slot 2's list is empty, append 12:

Insert 22. h(22) = 2. Slot 2 already has 12, append 22 to the end of its list:

Insert 7. h(7) = 2. Append 7 to slot 2's list:

Insert 17. h(17) = 2. Append 17 to slot 2's list:

Insert 5. h(5) = 0. Slot 0's list is empty, append 5 there instead, no collision:

Insert 13. h(13) = 3. Slot 3's list is empty, append 13 there:

Key	h(key)	Slot's list after insert
`12`	2	`12`
`22`	2	`12, 22`
`7`	2	`12, 22, 7`
`17`	2	`12, 22, 7, 17`
`5`	0	`5`
`13`	3	`13`

Unlike open addressing (linear/quadratic/double probing), chaining never runs out of room, since a slot's list can grow arbitrarily long, so the table never "fills up" the way an open-addressed table can. The trade-off is the extra memory for list pointers, and search time that depends on how long the chain at that slot has grown.

Comparing the four methods

Method	Family	Clustering	Notes
Linear probing	Open addressing	Primary clustering (worst)	Simplest, fastest per-probe
Quadratic probing	Open addressing	Secondary clustering	Better spread than linear
Double hashing	Open addressing	Minimal	Needs a second hash function
Chaining	Open hashing	None (separate lists)	Never "full," extra memory for pointers

Quick recall

A collision happens when two different keys hash to the same table slot; resolution finds where the second key actually goes.
Linear probing: step +1 each try; simplest but suffers primary clustering.
Quadratic probing: step +1², +2², +3², ...; avoids primary clustering but has secondary clustering (same start slot → same sequence).
Double hashing: step size comes from a second hash function h2(key); avoids both clustering types, strongest open-addressing method.
Chaining (open hashing): colliding keys form a linked list at that slot; never runs out of room, unlike the three probing methods.

That covers every topic in Module 4. For a focused list of the questions most likely to appear from this module, see Most Expected Questions.