# Hashing Tutorial

## Section 6.3 - Quadratic Probing

Another probe function that eliminates
primary clustering is called
**quadratic probing**.
Here the probe function is some quadratic function
**p**(*K*, *i*) = *c*_{1} *i*^{2}
+ *c*_{2} *i* + *c*_{3}
for some choice of constants *c*_{1}, *c*_{2},
and *c*_{3}.

The simplest variation is **p**(*K*, *i*) = *i*^{2}
(i.e., *c*_{1} = 1, *c*_{2} = 0, and
*c*_{3} = 0).
Then the *i*th value in the probe sequence would be
(**h**(*K*) + *i*^{2}) mod *M*.
Under quadratic probing, two keys with different home
positions will have diverging probe sequences.
For example, given a hash table of size *M* = 101, assume
for keys *k*_{1} and *k*_{2} that
and **h**(*k*_{1}) = 30 and
**h**(*k*_{2}) = 29.
The probe sequence for *k*_{1} is 30,
then 31, then 34, then 39.
The probe sequence for *k*_{2} is 29,
then 30, then 33, then 38.
Thus, while *k*_{2} will probe to *k*_{1}'s
home position as its second choice, the two keys' probe sequences
diverge immediately thereafter.

Try inserting numbers for yourself, and demonstrate how the probe sequences for diverge by inserting these numbers into a table of size 16: 0, 16, 32, 15, 31.

Unfortunately, quadratic probing has the disadvantage that typically
not all hash table slots will be on the probe sequence.
Using **p**(*K*, *i*) = *i*^{2}
gives particularly inconsistent results.
For many hash table sizes, this probe function will cycle through a
relatively small number of slots.
If all slots on that cycle happen to be full, this means that the
record cannot be inserted at all!
For example, if our hash table has three slots, then records that hash
to slot 0 can probe only to slots 0 and 1 (that is, the probe sequence
will never visit slot 2 in the table).
Thus, if slots 0 and 1 are full, then the record cannot be inserted
even though the table is not full!
A more realistic example is a table with 105 slots.
The probe sequence starting from any given slot will only visit 23
other slots in the table.
If all 24 of these slots should happen to be full, even if other slots
in the table are empty, then the record cannot be inserted because the
probe sequence will continually hit only those same 24 slots.

Now go back up to the applet above. Pick some hash table size, and try to insert values that all hash to the same slot. See how they follow a probe sequence that will not fill the table. Try to 'fill the probe sequence' such that a record cannot be inserted into the table, even though the table is not full.

Fortunately, it is possible to get good results from quadratic probing
at low cost.
The right combination of probe function and table size will visit many
slots in the table.
In particular, if the hash table size is a prime number and the probe
function is **p**(*K*, *i*) = *i*^{2},
then at least half the slots in the table will be visited.
Thus, if the table is less than half full, we can be certain that a
free slot will be found.
Alternatively, if the hash table size is a power of two and the probe
function is **p**(*K*, *i*) = (*i*^{2} + *i*)/2,
then every slot in the table will be visited by the probe function.

This applet will show you how well quadratic probing does (and doesn't) reach all the slots of a hash table. Try some different table sizes, and see how well each works. Try to find some hash table size that visits most of the slots.