A+DS

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

  1. 1Compute h(key) = key mod tableSize
  2. 2If the slot is empty, insert there
  3. 3If collision, probe (h+1²), (h+2²), (h+3²), ...
  4. 4Jump sizes grow: 1, 4, 9, 16, ... avoiding clusters

Loading...