page240.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 67 行
HTML
67 行
<HTML><HEAD><TITLE>Quadratic Probing</TITLE></HEAD><BODY bgcolor="#FFFFFF"> <a href="../index.html" target="_top"><img src="../icons/usins.gif" alt="Logo" align=right></a><b>Data Structures and Algorithms with Object-Oriented Design Patterns in Python</b><br><A NAME="tex2html3966" HREF="page241.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html3964" HREF="page238.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html3958" HREF="page239.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html3968" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H2><A NAME="SECTION008620000000000000000">Quadratic Probing</A></H2><P>An alternative to linear probing that addresses the primary clusteringproblem is called <em>quadratic probing</em><A NAME=13244> </A>.In quadratic probing, the function <I>c</I>(<I>i</I>)is a quadratic function in <I>i</I>.<A NAME="tex2html406" HREF="footnode.html#13245"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/foot_motif.gif"></A>The general quadratic has the form<P> <IMG WIDTH=318 HEIGHT=19 ALIGN=BOTTOM ALT="displaymath62431" SRC="img990.gif" ><P>However, quadratic probing is usually done using <IMG WIDTH=58 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline62437" SRC="img991.gif" >.<P>Clearly, <IMG WIDTH=58 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline62437" SRC="img991.gif" > satisfies property 1.What is not so clear is whether it satisfies property 2.In fact, in general it does not.The following theorem gives the conditions under which quadratic probing works:<P><BLOCKQUOTE> <b>Theorem</b><A NAME="theoremhashingi"> </A>When quadratic probing is used in a table of size <I>M</I>,where <I>M</I> is a prime number,the first <IMG WIDTH=41 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline62445" SRC="img992.gif" > probes are distinct.</BLOCKQUOTE><P> extbfProof (By contradiction).Let us assume that the theorem is false.Then there exist two distinct values <I>i</I> and <I>j</I>such that <IMG WIDTH=129 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline62451" SRC="img993.gif" >,that probe exactly the same position.Thus,<P> <IMG WIDTH=500 HEIGHT=112 ALIGN=BOTTOM ALT="eqnarray13251" SRC="img994.gif" ><P><P>Since <I>M</I> is a prime number,the only way that the product (<I>i</I>-<I>j</I>)(<I>i</I>+<I>j</I>) can be zero modulo <I>M</I>is for either <I>i</I>-<I>j</I> to be zero or <I>i</I>+<I>j</I> to be zero modulo <I>M</I>.Since <I>i</I> and <I>j</I> are distinct, <IMG WIDTH=62 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline62469" SRC="img995.gif" >.Furthermore, since both <I>i</I> and <I>j</I> are less than <IMG WIDTH=41 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline62445" SRC="img992.gif" >,the sum <I>i</I>+<I>j</I> is less than <I>M</I>.Consequently, the sum cannot be zero.We have successfully argued an absurdity--if the theorem is false one of two quantities must be zero,neither of which can possibly be zero.Therefore, the original assumption is not correctand the theorem is true.<P>Applying Theorem <A HREF="page240.html#theoremhashingi"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>we get that quadratic probing works as long as the table size is primeand there are fewer than <I>n</I>=<I>M</I>/2 items in the table.In terms of the load factor <IMG WIDTH=64 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline62233" SRC="img935.gif" >,this occurs when <IMG WIDTH=38 HEIGHT=29 ALIGN=MIDDLE ALT="tex2html_wrap_inline62485" SRC="img996.gif" >.<P>Quadratic probing eliminates the primary clustering phenomenonof linear probing because instead of doing a linear search,it does a quadratic search:<P> <IMG WIDTH=500 HEIGHT=118 ALIGN=BOTTOM ALT="eqnarray13256" SRC="img997.gif" ><P><HR><A NAME="tex2html3966" HREF="page241.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html3964" HREF="page238.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html3958" HREF="page239.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html3968" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <P><ADDRESS><img src="../icons/bruno.gif" alt="Bruno" align=right><a href="../copyright.html">Copyright © 2003</a> by <a href="../signature.html">Bruno R. Preiss, P.Eng.</a> All rights reserved.</ADDRESS></BODY></HTML>⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?