Java Reference
In-Depth Information
0
9050
0
9050
1
1001
1
1001
2
2
3
3
4
4
5
5
6
6
7
9877
7
9877
8
2037
8
2037
9
9
1059
(A)
(B)
Figure9.8
Example of problems with linear probing. (a) Four values are inserted
in the order 1001, 9050, 9877, and 2037 using hash function h(K) = K mod 10.
(b) The value 1059 is added to the hash table.
manner, records hashing to slots 7 or 8 will end up in slot 9. However, only records
hashing to slot 3 will be stored in slot 3, yielding one chance in ten of this happen-
ing. Likewise, there is only one chance in ten that the next record will be stored
in slot 4, one chance in ten for slot 5, and one chance in ten for slot 6. Thus, the
resulting probabilities are not equal.
To make matters worse, if the next record ends up in slot 9 (which already has
a higher than normal chance of happening), then the following record will end up
in slot 2 with probability 6/10. This is illustrated by Figure 9.8(b). This tendency
of linear probing to cluster items together is known as primary clustering. Small
clusters tend to merge into big clusters, making the problem worse. The objection
to primary clustering is that it leads to long probe sequences.
Improved Collision Resolution Methods
How can we avoid primary clustering? One possible improvement might be to use
linear probing, but to skip slots by a constant c other than 1. This would make the
probe function
p(K;i) = ci;
and so the ith slot in the probe sequence will be (h(K) + ic) mod M. In this way,
records with adjacent home positions will not follow the same probe sequence. For
example, if we were to skip by twos, then our offsets from the home slot would
be 2, then 4, then 6, and so on.
