Hash Table (Quadratic Probing)
Spread collisions out with quadratic jumps.
Quadratic probing is like linear probing, but instead of checking the next slot sequentially, it jumps by increasing squares: h+1², h+2², h+3², etc. This helps avoid the "clustering" problem where many consecutive slots fill up.
h(22) = 22 mod 7 = 1
Collision at 1? Try:
(1 + 1²) mod 7 = 2
(1 + 2²) mod 7 = 5
(1 + 3²) mod 7 = 3
Jumps: +1 +4 +9 +16 ...
Avoids clustering!How it works
- 1Compute h(key) = key mod tableSize
- 2If the slot is empty, insert there
- 3If collision, probe (h+1²), (h+2²), (h+3²), ...
- 4Jump sizes grow: 1, 4, 9, 16, ... avoiding clusters
Loading...