Java Reference
In-Depth Information
(a)
(b)
(c)
figure 20.6
Illustration of primary clustering in linear probing (b) versus no clustering (a) and the less significant secondary
clustering in quadratic probing (c). Long lines represent occupied cells, and the load factor is 0.7.
analysis indicated. The main difference occurs as
λ
gets close to 1. For
Primary clustering
is a problem at high
load factors. For
half-empty tables,
the effect is not
disastrous.
instance, if the table is 90 percent full,
= 0.9. The naive analysis suggests
that 10 cells would have to be examined—a lot but not completely out of the
question. However, by Theorem 20.2, the real answer is that some 50 cells
need to be examined. That is excessive (especially as this number is only an
average and thus some insertions must be worse).
λ
20.3.3
analysis of the
find
operation
The cost of an insertion can be used to bound the cost of a
find
. There are two
types of
find
operations: unsuccessful and successful. An unsuccessful
find
is
easy to analyze. The sequence of slots examined for an unsuccessful search of
X
is the same as the sequence examined to
insert
X
. Thus we have an immedi-
ate answer for the cost of an unsuccessful
find
.
An unsuccessful
find
costs the
same as an
insertion.
For successful
find
s, things are slightly more complicated. Figure 20.5
shows a table with
The cost of a suc-
cessful
find
is an
average of the
insertion costs over
all smaller load
factors.
= 0.5. Thus the average cost of an insertion is 2.5.
The average cost to
find
the newly inserted item would then be 2.5, no
matter how many insertions follow. The average cost to find the first item
inserted in the table is always 1.0 probe. Thus, in a table with
λ
= 0.5,
some searches are easy and some are hard. In particular, the cost of a suc-
cessful search of
X
is equal to the cost of inserting
X at the time X was
inserted.
To find the average time to perform a successful search in a table
with load factor
λ
,
we must compute the average insertion cost by averag-
ing over all the load factors leading to
λ
λ
. With this groundwork, we can
Search WWH ::
Custom Search