Linear Probing

Problem: primary clustering - collisions tend to cause clusters of occupied buckets.
The larger the cluster gets, the higher the probabilility that it will grow.

Impact of Load Factor on Cost

Dashed lines are linear probing, solid lines are “random” probing.

Load factor is on the x-axis, expected number of buckets accessed on the y-axis.

Probe function: \(p(K, i) = c_1 \times i + c_2 \times i^2\)
Bucket to access: \(h(K) + p(K, i)\), where:
- \(K\) - original key
- \(h(K)\) - result of hashing the key
- \(p(K, i)\) - offset from the original hash location to check after \(i\) collisions
For example, assuming \(c_1 = 1, c_2 = 1\):
- After one collision: \(p(K, 1) = 1 + 1 = 2\)
- After two collisions: \(p(K, 2) = 2 + 4 = 6\)
- After three collisions: \(p(K, 3) = 3 + 9 = 12\)
- After four collisions: \(p(K, 4) = 4 + 16 = 20\)
Problem:
- Secondary Clustering: Keys that hash to the same bucket will follow the same probe sequence.

Probe function: \(p(K, i) = h_2(K) \times i\)
Example with \(h_2(K) = 1 + K \% 10\)
- After one collision for \(K=14\): \(p(K, 1) = 5 \times 1 = 5\)
- After two collisions for \(K=14\): \(p(K, 2) = 5 \times 2 = 10\)
- After three collisions for \(K=14\): \(p(K, 3) = 5 \times 3 = 15\)
Different keys follow different probe sequences, so this is resistant to both primary and secondary clustering.