Collision resolution techniques in hashing

A collision occurs when two different keys hash to the same table location, i.e. h(k1) = h(k2) for k1 ≠ k2. For example, with h(k) = k mod 10, keys 42 and 52 both map to location 2. A collision resolution technique decides where the second key is stored.

Methods are in two groups.

1. Open addressing (closed hashing)

All keys stay inside the table. If the home location is full, other locations are probed in a fixed sequence.

• Linear probing: h(k, i) = (h(k) + i) mod m. Try the next slot, then the next, and so on. Simple, but causes primary clustering (long runs of filled slots).
• Quadratic probing: h(k, i) = (h(k) + c₁i + c₂i²) mod m, e.g. +1, +4, +9. Reduces primary clustering, but keys with the same home slot follow the same path (secondary clustering).
• Double hashing: h(k, i) = (h1(k) + i·h2(k)) mod m. The step depends on the key, so clustering is much lower.

Example (m = 10, h(k) = k mod 10, keys 42, 52, 62):

2. Separate chaining (open hashing)

Each table location holds a linked list of all keys that hash there. A colliding key is simply added to the list.

0 -> NULL
2 -> 42 -> 52 -> 62 -> NULL
3 -> 13 -> NULL

• Table never overflows; deletion is easy.
• Needs extra memory for pointers; search is O(1 + α) where α = n/m is the load factor.

Other schemes are rehashing and coalesced chaining. Open addressing needs a load factor below 1, while chaining works for any load factor.