OBHTs: choosing the step length
To resolve a collision, the search/insertion/deletion algorithm increments the bucket index and tries again.
The step length, s, is the amount by which the bucket index is incremented. So far we have assumed s = 1.
Alternatively, we can use a fixed s > 1.
Choose m to be prime, and choose s to be in the range 2…m–1.
- This ensures that s and m have no common factors.
- Otherwise, if (say) m = 10 and s = 2, a typical search path would be 6–8–0–2–4, never reaching the remaining buckets!