Quadratic Probing
On collision, probe at home+1², home+2², home+3²... instead of a fixed step. Spreads out primary clustering, though keys sharing a home slot still share the same probe sequence (secondary clustering).
- Category
- Hashing
- Time complexity
- O(1) avg
- Space complexity
- O(n)
Pseudocode
i = 0 while table[(home + i²) % size] occupied: i += 1 insert at (home + i²) % size
Reference implementation
i = 0
while table[(home + i*i) % size] is not None:
i += 1
table[(home + i*i) % size] = key