Java Reference
In-Depth Information
Double hashing, like other open addressing schemes, should produce a probe sequence that
reaches the entire table. Such will be the case if the size of the hash table is a prime number. (See
Exercise 9 at the end of this chapter.) The second hash function must be different from the origi-
nal hash function and must never have a zero value, since zero is not an appropriate increment.
21.21
Example.
For example, consider the following pair of hash functions for a hash table whose size is 7:
h
1
(key)
=
key modulo
7
h
2
(key)
=
5
-
key modulo
5
This hash table is unusually small, but it allows us to study the behavior of the probe sequence. For
a search key of 16, we have
h
1
(16)
=
2
h
2
(16)
=
4
The probe sequence begins at 2 and probes locations at increments of 4, as Figure 21-8 illustrates.
Remember that when probing reaches the end of the table, it continues at the table's beginning. The table
locations in the probe sequence then have the following indices: 2, 6, 3, 0, 4, 1, 5, 2, …. This sequence
reaches all locations in the table and then repeats itself. Notice that the table size, 7, is a prime number.
FIGURE 21-8
The first three locations in a probe sequence generated by double
hashing for the search key 16
(a)
(b)
(c)
0
0
1
0
1
1
2
2
h
1
(16)
2
3
4
5
3
3
h
1
(16)
2
h
2
(16)
4
4
5
5
h
1
(16)
h
2
(16)
6
6
6
What happens if we change the size of the table to 6 and use the hash functions
h
1
(
key
)
=
key
modulo 6
h
2
(
key
)
=
5
-
key
modulo 5
For a search key of 16, we have
h
1
(16)
=
4
h
2
(16)
=
4
The probe sequence begins at 4 and probes locations at increments of 4. The sequence's indices are
then 4, 2, 0, 4, 2, 0, …. The probe sequence does not reach all table locations before it begins to
repeat. Notice that the table size, 6, is not prime.
