Java Reference
In-Depth Information
Table 10-1. Search Length Increases as the Table Fills Up
Successful
Search Length
Unsuccessful
Search Length
f
0.25
1.2
1.4
0.50
1.5
2.5
0.75
2.5
8.5
0.90
5.5
50.5
At 90 percent full, the average successful search length is a reasonable 5.5. However, it can take quite long
(50.5 probes) to determine that a new key is not in the table. If linear probe is being used, it would be wise to ensure
that the table does not become more than about 75 percent full. This way, we can guarantee good performance with a
simple algorithm.
10.3.2 Quadratic Probing
In this method, suppose an incoming key collides with another at location loc ; we go forward ai + bi 2 where a , b are
constants and i takes on the value 1 for the first collision, 2 if the key collides again, 3 if it collides yet again, and so on.
For example, if we let a = 1 and b =1, we go forward i + i 2 from location loc . Suppose the initial hash location is 7 and
there is a collision.
We calculate i + i 2 with i = 1; this gives 2, so we go forward by 2 and check location 7 + 2 = 9.
If there is still a collision, we calculate i + i 2 with i = 2; this gives 6, so we go forward by 6 and check location 9 + 6 = 15.
If there is still a collision, we calculate i + i 2 with i = 3; this gives 12, so we go forward by 12 and check
location 15 + 12 = 27.
And so on. Each time we get a collision, we increase i by 1 and recalculate how much we must go forward this
time. We continue this way until we find the key or an empty location.
If, at any time, going forward takes us beyond the end of the table, we wrap around to the beginning. For example,
if the table size is 25 and we go forward to location 27, we wrap to location 27 - 25, that is, location 2.
For the next incoming key, if there is a collision at the initial hash location, we set i to 1 and continue as explained
earlier. It is worth noting that, for each key, the sequence of “increments” will be 2, 6, 12, 20, 30.... We can, of course,
get a different sequence by choosing different values for a and b .
We can summarize the process just described with the following algorithm:
//find or insert 'key' in the hash table, num[1..n]
loc = H(key)
i = 0
while (num[loc] != Empty && num[loc] != key) {
i = i + 1
loc = loc + a * i + b * i * i
while (loc > n) loc = loc - n //while instead of if; see note below
}
if (num[loc] == Empty) num[loc] = key
else print key, " found in location ", loc
 
Search WWH ::




Custom Search