📄 page216.html

📁 Data Structures And Algorithms With Object-Oriented Design Patterns In Python (2003) source code and
💻 HTML
字号:
<HTML><HEAD><TITLE>Fibonacci Hashing</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="tex2html3689" HREF="page217.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html3687" HREF="page212.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html3683" HREF="page215.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A>  <A NAME="tex2html3691" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H2><A NAME="SECTION008240000000000000000">Fibonacci Hashing</A></H2><P>The final variation of hashing to be considered hereis called the <em>Fibonacci hashing method</em><A NAME=10649>&#160;</A><A NAME=10650>&#160;</A>.In fact, Fibonacci hashing is exactly the multiplication hashing methoddiscussed in the preceding section using a very special value for <I>a</I>.The value we choose is closely related to the number called the golden ratio.<P>The <em>golden ratio</em><A NAME=10652>&#160;</A> is defined as follows:Given two positive numbers <I>x</I> and <I>y</I>,the ratio  <IMG WIDTH=55 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline61795" SRC="img857.gif"  > is the golden ratio ifthe ratio of <I>x</I> to <I>y</I> is the same as that of <I>x</I>+<I>y</I> to <I>x</I>.The value of the golden ratio can be determined as follows:<P> <IMG WIDTH=500 HEIGHT=100 ALIGN=BOTTOM ALT="eqnarray10653" SRC="img858.gif"  ><P>There is an intimate relationship between the golden ratio and theFibonacci numbers<A NAME=10661>&#160;</A>.In Section&nbsp;<A HREF="page75.html#secfibonacci"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> it was shown that the  <IMG WIDTH=21 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline57913" SRC="img94.gif"  > Fibonaccinumber is given by<P> <IMG WIDTH=318 HEIGHT=38 ALIGN=BOTTOM ALT="displaymath61787" SRC="img859.gif"  ><P>where  <IMG WIDTH=106 HEIGHT=30 ALIGN=MIDDLE ALT="tex2html_wrap_inline59943" SRC="img486.gif"  > and  <IMG WIDTH=106 HEIGHT=32 ALIGN=MIDDLE ALT="tex2html_wrap_inline59945" SRC="img487.gif"  >!<P>The Fibonacci hashing methodis essentially the multiplication hashing methodin which the constant <I>a</I>is chosen as the integer that is relatively prime to <I>W</I>which is closest to  <IMG WIDTH=31 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline61815" SRC="img860.gif"  >.The following table gives suitable values of <I>a</I>for various word sizes.<DIV ALIGN=CENTER><P ALIGN=CENTER><TABLE COLS=2 BORDER FRAME=HSIDES RULES=GROUPS><COL ALIGN=CENTER><COL ALIGN=RIGHT><TBODY><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>    <I>W</I> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP COLSPAN=1>  <IMG WIDTH=63 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline61821" SRC="img861.gif"  ></TD></TR></TBODY><TBODY><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=19 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline61823" SRC="img862.gif"  > </TD><TD VALIGN=BASELINE ALIGN=RIGHT NOWRAP> 40503</TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>      <IMG WIDTH=20 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline61825" SRC="img863.gif"  > </TD><TD VALIGN=BASELINE ALIGN=RIGHT NOWRAP> 2654435769 </TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>      <IMG WIDTH=19 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline61827" SRC="img864.gif"  > </TD><TD VALIGN=BASELINE ALIGN=RIGHT NOWRAP> 11400714819323198485 </TD></TR></TBODY></TABLE></P></DIV><P>Why is  <IMG WIDTH=31 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline61815" SRC="img860.gif"  > special?It has to do with what happens to consecutive keyswhen they are hashed using the multiplicative method.As shown in Figure&nbsp;<A HREF="page216.html#figgolden"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>,consecutive keys are spread out quite nicely.In fact, when we use  <IMG WIDTH=63 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline61821" SRC="img861.gif"  > to hash consecutive keys,the hash value for each subsequent key fallsin between the two widest spaced hash values already computed.Furthermore, it is a property of the golden ratio,  <IMG WIDTH=8 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline61833" SRC="img865.gif"  >,that each subsequent hash value divides the interval into which it fallsaccording to the golden ratio!<P><P><A NAME="10729">&#160;</A><A NAME="figgolden">&#160;</A> <IMG WIDTH=575 HEIGHT=322 ALIGN=BOTTOM ALT="figure10682" SRC="img866.gif"  ><BR><STRONG>Figure:</STRONG> Fibonacci hashing.<BR><P><HR><A NAME="tex2html3689" HREF="page217.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html3687" HREF="page212.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html3683" HREF="page215.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A>  <A NAME="tex2html3691" 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 &#169; 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 + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -