# 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 *i*th slot in the probe sequence is
(**h**(*K*) + *r*_{i}) mod *M*
where *r*_{i} is the *i*th 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.