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) = c1 i2 + c2 i + c3 for some choice of constants c1, c2, and c3.
The simplest variation is p(K, i) = i2 (i.e., c1 = 1, c2 = 0, and c3 = 0). Then the ith value in the probe sequence would be (h(K) + i2) 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 k1 and k2 that and h(k1) = 30 and h(k2) = 29. The probe sequence for k1 is 30, then 31, then 34, then 39. The probe sequence for k2 is 29, then 30, then 33, then 38. Thus, while k2 will probe to k1'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) = i2 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) = i2, 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) = (i2 + 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.
