📄 page246.html
字号:
<HTML>
<HEAD>
<TITLE>Average Case Analysis</TITLE>
</HEAD>
<BODY bgcolor="#FFFFFF">
<img src="cover75.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cover75.gif" alt="Logo" align=right>
<b>Data Structures and Algorithms
with Object-Oriented Design Patterns in C++</b><br>
<A NAME="tex2html4955" HREF="page247.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page247.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="next_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/next_motif.gif"></A> <A NAME="tex2html4953" HREF="page237.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page237.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="up_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/up_motif.gif"></A> <A NAME="tex2html4949" HREF="page245.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page245.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="previous_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/previous_motif.gif"></A> <A NAME="tex2html4957" HREF="page9.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page9.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="contents_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/contents_motif.gif"></A> <A NAME="tex2html4958" HREF="page620.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page620.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="index_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/index_motif.gif"></A> <BR><HR>
<H2><A NAME="SECTION009650000000000000000">Average Case Analysis</A></H2>
<P>
The average case analysis of open addressing is easy if we
ignore the primary clustering phenomenon.
Given a scatter table of size <I>M</I> that contains <I>n</I> items,
we assume that each of the <IMG WIDTH=24 HEIGHT=31 ALIGN=MIDDLE ALT="tex2html_wrap_inline63244" SRC="img1062.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1062.gif" > combinations of <I>n</I> occupied
and (<I>m</I>-<I>n</I>) empty scatter table entries is equally likely.
This is the so-called
<em>uniform hashing model</em><A NAME=14145> </A>.
<P>
In this model we assume that the entries will either be
occupied or empty, i.e., the <tt>deleted</tt> state is not used.
Suppose a search for an empty cell requires exactly <I>i</I> probes.
Then the first <I>i</I>-1 positions probed must have been occupied
and the <IMG WIDTH=17 HEIGHT=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline58387" SRC="img77.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img77.gif" > position probed was empty.
Consider the <I>i</I> cells which were probed.
The number of combinations in which <I>i</I>-1 of the probed cells are occupied
and one is empty is <IMG WIDTH=49 HEIGHT=32 ALIGN=MIDDLE ALT="tex2html_wrap_inline63260" SRC="img1063.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1063.gif" >.
Therefore, the probability that exactly <I>i</I> probes are required is
<P><A NAME="eqnhashingprob"> </A> <IMG WIDTH=500 HEIGHT=46 ALIGN=BOTTOM ALT="equation14150" SRC="img1064.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1064.gif" ><P>
<P>
The average number of probes required to find an empty cell
in a table which has <I>n</I> occupied cells is <I>U</I>(<I>n</I>) where
<P><A NAME="eqnhashingu"> </A> <IMG WIDTH=500 HEIGHT=47 ALIGN=BOTTOM ALT="equation14157" SRC="img1065.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1065.gif" ><P>
Using Equation <A HREF="page246.html#eqnhashingprob" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page246.html#eqnhashingprob"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> into Equation <A HREF="page246.html#eqnhashingu" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page246.html#eqnhashingu"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>
and simplifying the result gives
<P><A NAME="eqnhashinguuu"> </A><A NAME="eqnhashinguu"> </A> <IMG WIDTH=500 HEIGHT=121 ALIGN=BOTTOM ALT="eqnarray14164" SRC="img1066.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1066.gif" ><P>
This result is actually quite intuitive.
The load factor, <IMG WIDTH=8 HEIGHT=11 ALIGN=BOTTOM ALT="tex2html_wrap_inline62866" SRC="img985.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img985.gif" >, is the fraction of occupied entries.
Therefore, <IMG WIDTH=36 HEIGHT=20 ALIGN=MIDDLE ALT="tex2html_wrap_inline63272" SRC="img1067.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1067.gif" > entries are empty
so we would expect to have to probe <IMG WIDTH=63 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline63274" SRC="img1068.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1068.gif" > entries
before finding an empty one!
E.g., if the load factor is 0.75,
a quarter of the entries are empty.
Therefore, we expect to have to probe four entries before finding an empty one.
<P>
To calculate the average number of probes for a successful search
we make the observation that when an item is initially inserted,
we need to find an empty cell in which to place it.
E.g., the number of probes to find the empty position into which
the <IMG WIDTH=17 HEIGHT=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline58387" SRC="img77.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img77.gif" > item is to be placed is <I>U</I>(<I>i</I>).
And this is exactly the number of probes it takes
to find the <IMG WIDTH=17 HEIGHT=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline58387" SRC="img77.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img77.gif" > item again!
Therefore, the average number of probes required for a successful search
in a table which has <I>n</I> occupied cells is <I>S</I>(<I>n</I>) where
<P><A NAME="eqnhashings"> </A> <IMG WIDTH=500 HEIGHT=46 ALIGN=BOTTOM ALT="equation14177" SRC="img1069.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1069.gif" ><P>
Substituting Equation <A HREF="page246.html#eqnhashinguu" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page246.html#eqnhashinguu"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> in Equation <A HREF="page246.html#eqnhashings" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page246.html#eqnhashings"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>
and simplifying gives
<P><A NAME="eqnhashingss"> </A> <IMG WIDTH=500 HEIGHT=122 ALIGN=BOTTOM ALT="eqnarray14186" SRC="img1070.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1070.gif" ><P>
where <IMG WIDTH=20 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline63286" SRC="img1071.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1071.gif" > is the <IMG WIDTH=20 HEIGHT=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline61700" SRC="img803.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img803.gif" > <em>harmonic number</em><A NAME=14204> </A>
(see Section <A HREF="page44.html#secmodelharmonic" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page44.html#secmodelharmonic"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>).
Again, there is an easy intuitive derivation for this result.
We can use a simple integral to calculate the mean number of probes
for a successful search using the approximation <IMG WIDTH=119 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline63290" SRC="img1072.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1072.gif" > as follows
<P> <IMG WIDTH=500 HEIGHT=129 ALIGN=BOTTOM ALT="eqnarray14206" SRC="img1073.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1073.gif" ><P>
<P>
Empirical evidence has shown that
the formulas derived for the <em>uniform hashing model</em>
characterize the performance of scatter tables using open addressing with
quadratic probing and double hashing quite well.
However, they do not capture the effect of primary clustering
which occurs when linear probing is used.
Knuth has shown that when primary clustering is taking into account,
the number of probes required to locate an empty cell is
<P><A NAME="eqnhashinguknuth"> </A> <IMG WIDTH=500 HEIGHT=48 ALIGN=BOTTOM ALT="equation14223" SRC="img1074.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1074.gif" ><P>
and the number of probes required for a successful search is
<P><A NAME="eqnhashingsknuth"> </A> <IMG WIDTH=500 HEIGHT=38 ALIGN=BOTTOM ALT="equation14230" SRC="img1075.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1075.gif" ><P>
<P>
The graph in Figure <A HREF="page246.html#figscatter" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page246.html#figscatter"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>
compares the predictions of the uniform hashing model
(Equations <A HREF="page246.html#eqnhashinguuu" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page246.html#eqnhashinguuu"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> and <A HREF="page246.html#eqnhashingss" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page246.html#eqnhashingss"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>)
with the formulas derived by Knuth
(Equations <A HREF="page246.html#eqnhashinguknuth" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page246.html#eqnhashinguknuth"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> and <A HREF="page246.html#eqnhashingsknuth" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page246.html#eqnhashingsknuth"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>).
Clearly, while the results are qualitatively similar,
the formulas are in agreement for small load factors
and they diverge as the load factor increases.
<P>
<P><A NAME="14528"> </A><A NAME="figscatter"> </A> <IMG WIDTH=575 HEIGHT=383 ALIGN=BOTTOM ALT="figure14242" SRC="img1076.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1076.gif" ><BR>
<STRONG>Figure:</STRONG> Number of Probes vs. Load Factor for Uniform Hashing and Linear Probing<BR>
<P><HR><A NAME="tex2html4955" HREF="page247.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page247.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="next_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/next_motif.gif"></A> <A NAME="tex2html4953" HREF="page237.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page237.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="up_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/up_motif.gif"></A> <A NAME="tex2html4949" HREF="page245.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page245.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="previous_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/previous_motif.gif"></A> <A NAME="tex2html4957" HREF="page9.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page9.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="contents_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/contents_motif.gif"></A> <A NAME="tex2html4958" HREF="page620.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page620.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="index_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/index_motif.gif"></A> <P><ADDRESS>
<img src="bruno.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/bruno.gif" alt="Bruno" align=right>
<a href="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address. \n\nDo you want to open it from the server?'))window.location='http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html">Copyright © 1997</a> by <a href="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address. \n\nDo you want to open it from the server?'))window.location='http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html">Bruno R. Preiss, P.Eng.</a> All rights reserved.
</ADDRESS>
</BODY>
</HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -