Java Reference
In-Depth Information
You can avoid primary clustering by changing the probe sequence that you use to resolve a colli-
sion. As we discussed in the previous section, if a given search key hashes to index
k
, linear prob-
ing looks at the consecutive locations beginning at index
k
.
Quadratic probing
,
on the other hand,
considers the locations at indices
k
+
j
2
for
j
0—that is, it uses the indices
k
,
k
+
1,
k
+
4,
k
+
9, and
so on. As before, if the probe sequence reaches the end of the hash table, it wraps around to the
beginning of the table. This open addressing scheme separates the entries in the probe sequence,
after the first two. In fact, this separation increases as the sequence grows in length. Figure 21-7
highlights the locations in a hash table that form one such probe sequence of five entries.
≥
FIGURE 21-7
A probe sequence of length five using quadratic probing
k
2
2
k
3
2
k
4
2
k
k
1
Except for the change in probe sequence, quadratic probing is like linear probing. It uses the
three states that Segment 21.16 describes: occupied, empty, and available. Additionally, it reuses
table locations in the available state, as described in Segment 21.17.
Although quadratic probing avoids primary clustering, entries that collide with an existing table
entry use the same probe sequence, thereby increasing its length. This phenomenon—called
secondary
clustering
—is usually not a serious problem, but it increases search times.
An advantage of linear probing is that it can reach every location in the hash table. As we
mentioned earlier, this property is important since it guarantees the success of the
add
operation
when the hash table is not full. Quadratic probing can also guarantee a successful
add
opera-
tion, as long as the hash table is at most half full and its size is a prime number. (See Exercise 8
at the end of this chapter.)
Quadratic probing requires more effort to compute the indices for the probe sequence than
does linear probing. Exercise 2 at the end of this chapter shows how to compute these indices
without multiplications or divisions.
Note:
Quadratic probing
•
Resolves a collision during hashing by examining locations in the hash table at the
original hash index plus
j
2
, for
j
≥
0
•
Reaches half of the locations in the hash table if the size of the table is a prime number
•
Avoids primary clustering but can lead to secondary clustering
Beginning at the original hash index
k
, both linear probing and quadratic probing add increments
to
k
to define a probe sequence. These increments—1 for linear probing and
j
2
for quadratic
probing—are independent of the search key.
Double hashing
uses a second hash function to
compute these increments in a key-dependent way. In this way, double hashing avoids both pri-
mary and secondary clustering.
