Java Reference
In-Depth Information
compute the average search times for linear probing, as asserted and
proved in Theorem 20.3.
The average number of cells examined in an unsuccessful search using linear prob-
ing is roughly
Theorem 20.3
(
111λ
+
⁄
(
-
)
2
)
⁄
2
. The average number of cells examined in a suc-
cessful search is approximately
(
111λ
+
⁄
(
-
)
)
⁄
2
.
Proof
The cost of an unsuccessful search is the same as the cost of an insertion. For a suc-
cessful search, we compute the average insertion cost over the sequence of inser-
tions. Because the table is large, we can compute this average by evaluating
1
λ
λ
S
()
=
---
∫
I
()
d
x
= 0
In other words, the average cost of a successful search for a table with a load factor
of
equals the cost of an insertion in a table of load factor
x
, averaged from load fac-
tors 0 through
λ
λ
. From Theorem 20.2, we can derive the following equation:
1
λ
1
---
1
1
λ
⎛
⎞
S
()
=
+
d
---
∫
------------------
⎝
⎠
2
x
= 0
(
1
-
x
)
λ
1
2λ
1
⎛
⎞
=
------
x
+
----------------
⎝
⎠
(
1
-
x
)
x
= 0
1
2
1
⎛
⎛
⎞
⎞
=
λ
+
-
1
------
-----------------
⎝
⎝
⎠
⎠
λ
(
1
-
λ
)
1
---
2
-
λ
⎛
⎞
=
------------
⎝
⎠
1
-
λ
1
---
1
1
⎛
⎞
=
+
-----------------
⎝
⎠
(
1
-
λ
)
We can apply the same technique to obtain the cost of a successful
find
under the assumption of independence (by using in
Theorem 20.3). If there is no clustering, the average cost of a successful
find
for linear probing is . If the load factor is 0.5, the aver-
age number of probes for a successful search using linear probing is 1.5,
whereas the nonclustering analysis suggests 1.4 probes. Note that this
average does not depend on any ordering of the input keys; it depends
only on the fairness of the hash function. Note also that, even when we have
good hash functions, both longer and shorter probe sequences are bound
to contribute to the average. For instance, there are certain to be some
Ix
()
=
11
x
⁄
(
-
)
-
ln
(
1
-
λ
)
⁄
λ
Search WWH ::
Custom Search