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.

(From OpenDSA Data Structures and Algorithms book)

Solution #1: Quadratic Probing

• Probe function: \(p(K, i) = c_1 \times i^2 + c_2 \times i + c_3\)
• 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) = 4 + 2 = 6\)
  • After three collisions: \(p(K, 3) = 9 + 3 = 12\)
  • After four collisions: \(p(K, 4) = 16 + 14 = 20\)
• Problem:
  • Secondary Clustering: Keys that hash to the same bucket will follow the same probe sequence.

Solution #2: Double Hashing

• 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.