Java Reference
In-Depth Information
λ
increases—that is, as the hash table fills—the number of comparisons for these searches increases.
This result satisfies our initial intuition. For example, when the hash table is half full—that is, when
λ
After evaluating these expressions for a few values of
λ
, we get the results in Figure 22-1. As
is 0.5—an average unsuccessful search requires about 2.5 comparisons and an average successful
search requires about 1.5 comparisons. As
increases beyond 0.5, the number of comparisons for
an unsuccessful search increases much more rapidly than for a successful search. Thus, perfor-
mance degrades rapidly when the hash table is more than half full. Should this happen, you'd need
to define a larger hash table, as we describe a bit later in this chapter in the section “Rehashing.”
λ
Note: The performance of hashing with linear probing degrades significantly as the load
factor
increases. To maintain reasonable efficiency, the hash table should be less than half
full. That is, keep
λ
λ
< 0.5.
FIGURE 22-1
The average number of comparisons required by a search of
the hash table for given values of the load factor
λ
when using
linear probing
λ
Unsuccessful Search
Successful Search
0.1
0.3
0.5
0.7
0.9
1.1
1.5
2.5
6.1
50.5
1.1
1.2
1.5
2.2
5.5
22.5
Quadratic probing and double hashing. Secondary clustering as a result of quadratic probing is
not as serious as the primary clustering that occurs when you use linear probing. Here, the average
number of comparisons needed to search the probe sequence for a given search key is about
1
-----------------
for an unsuccessful search and
(
1
-
λ
)
1
1
λ
----------- © § ·
for a successful search
log
---
1
-
λ
that we used for linear prob-
ing. Notice that the number of comparisons for an unsuccessful search grows with
Figure 22-2 evaluates these expressions for the same values of
λ
λ
more rapidly
than for a successful search. Although, the degradation in performance as
λ
increases is not as
< 0.5 to maintain efficiency.
Even though double hashing avoids the clustering of linear probing and quadratic probing, the
estimate of its efficiency is the same as for quadratic probing.
severe as with linear probing, you still want
λ
Note: If you use quadratic probing or double hashing, the hash table should be less than
half full. That is,
λ
should be less than 0.5.
 
Search WWH ::




Custom Search