Java Reference
In-Depth Information
FIGURE 22-2
The average number of comparisons required by a search of the
hash table for given values of the load factor
λ
when using
either quadratic probing or double hashing
λ
Unsuccessful Search
Successful Search
0.1
0.3
0.5
0.7
0.9
1.1
1.4
2.0
3.3
10.0
1.1
1.2
1.4
1.7
2.6
With separate chaining as the collision resolution strategy, each entry in the hash table can refer-
ence a chain of linked nodes. The number of such chains, including empty ones, is then the size
of the hash table. Thus, the load factor
λ
is the number of dictionary entries divided by the num-
ber of chains. That is,
is the average number of dictionary entries per chain. Since this number
is an average, we expect some chains to contain fewer than
λ
entries—or even none—and some
to have more. We assume that the chains are not sorted and that the search keys in the dictionary
are distinct.
The dictionary operations
getValue
,
remove
, and
add
each require a search of the chain indi-
cated by the search key. As was the case for open addressing, analyzing the efficiency of these
searches is sufficient. Again, we will state the number of comparisons necessary to locate a search
key in the hash table in terms of the load factor
λ
.
An unsuccessful search of a hash table sometimes will encounter an empty chain, and so that
operation is O(1) and would be the best case. But for the average case when the chains are not
sorted, searching for an entry in the hash table without success examines
λ
nodes. In contrast, a suc-
cessful search always inspects a chain that is not empty. In addition to seeing that the table location
at the hash index is not
null
, an average successful search considers a chain of
λ
λ
nodes and locates
the desired entry after looking at
/
2 of them. Thus, the average number of comparisons during a
search when separate chaining is used is about
λ
λ
for an unsuccessful search
1
+
λ
/
2
for a successful search
, we get the results in Figure 22-3. The
number of comparisons for these searches increases only slightly as
After evaluating these expressions for a few values of
λ
λ
increases—that is, as the
hash table fills. A typical upper bound for
is 1, as smaller values do not provide significantly bet-
ter performance. Notice the unusual result: Successful searches take more time than unsuccessful
searches when
λ
<
2.
Remember that these results are for the average case. In the worst case, all search keys map
into the same table location. Thus, all entries occur in the same chain of nodes. The worst-case
search time, then, is O(
n
), where
n
is the number of entries.
λ
Note:
The average performance of hashing with separate chaining does not degrade signifi-
cantly as the load factor
λ
increases. To maintain reasonable efficiency, you should keep
λ
<
1.
