Linear Probing
On collision, scan forward one slot at a time (wrapping around) until an empty slot is found. Simple and cache-friendly, but prone to "primary clustering" — long runs of occupied slots that make future probes progressively longer.
- Category
- Hashing
- Time complexity
- O(1) avg
- Space complexity
- O(n)
Pseudocode
i = hash(key) % size while table[i] occupied: i = (i+1) % size table[i] = key
Reference implementation
i = hash(key) % size
while table[i] is not None:
i = (i + 1) % size
table[i] = key