Java Reference
In-Depth Information
Example9.9
Consider a table of size M = 101, with
Perm
[1] = 5,
Perm
[2] = 2, and
Perm
[3] = 32. Assume that we have two keys k
1
and
k
2
where h(k
1
) = 30 and h(k
2
) = 35. The probe sequence for k
1
is 30,
then 35, then 32, then 62. The probe sequence for k
2
is 35, then 40, then
37, then 67. Thus, while k
2
will probe to k
1
's home position as its second
choice, the two keys' probe sequences diverge immediately thereafter.
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 ith 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.
Example9.10
Given a hash table of size M = 101, assume for keys k
1
and k
2
that 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.
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 in-
consistent 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, then
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.
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
