Hashing Tutorial

Section 6.2 - Pseudo-random Probing

The ideal probe function would select the next position on the probe sequence at random from among the unvisited slots; that is, the probe sequence should be a random permutation of the hash table positions. Unfortunately, we cannot actually select the next position in the probe sequence at random, because we would not be able to duplicate this same probe sequence when searching for the key. However, we can do something similar called pseudo-random probing. In pseudo-random probing, the ith slot in the probe sequence is (h(K) + r_i) mod M where r_i is the ith value in a random permutation of the numbers from 1 to M-1. All insertions and searches use the same sequence of random numbers. The probe function would be p(K, i) = Perm[i-1] where Perm is an array of length M-1 containing a random permutation of the values from 1 to M - 1.

As you select values to insert, be sure to trigger collision resolution enough times to get an understanding of how pseudo-random probing works. Try hitting the "reset" button, and see how the random permutation being used will change.