📄 page214.html
字号:
<HTML><HEAD><TITLE>Middle Square Method</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="tex2html3669" HREF="page215.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html3667" HREF="page212.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html3661" HREF="page213.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html3671" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H2><A NAME="SECTION008220000000000000000">Middle Square Method</A></H2><P>In this section we consider a hashing methodwhich avoids the use of division.Since integer division is usually slower than integer multiplication,by avoiding division we can potentially improvethe running time of the hashing algorithm.We can avoid division by doing the arithmeticby using shifts and bitwise operations instead.<P>The <em>middle-square hashing method</em><A NAME=10619> </A><A NAME=10620> </A>works as follows.First, we assume that <I>M</I> is a power of two,say <IMG WIDTH=52 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline61633" SRC="img841.gif" > for some <IMG WIDTH=37 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59027" SRC="img353.gif" >.Then, to hash an integer <I>x</I>,we use the following hash function:<P> <IMG WIDTH=341 HEIGHT=39 ALIGN=BOTTOM ALT="displaymath61659" SRC="img844.gif" ><P>For <I>W</I> we use the <em>word size</em><A NAME=10624> </A> of the machine.That is <IMG WIDTH=60 HEIGHT=15 ALIGN=BOTTOM ALT="tex2html_wrap_inline61675" SRC="img845.gif" >.<P>Notice that since <I>M</I> and <I>W</I> are both powers of two,the ratio <IMG WIDTH=94 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline61681" SRC="img846.gif" > is also a power two.Therefore, in order to multiply the term <IMG WIDTH=83 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline61683" SRC="img847.gif" > by <I>M</I>/<I>W</I>we simply shift it to the right by <I>w</I>-<I>k</I> bits!In effect,we are extracting <I>k</I> bits from the middle of the square of the key--hence the name of the method.<P>The following code fragment illustratesthe middle-square method of hashing:<PRE>k = 10 # M==1024w = 32mask = (1 << k) - 1def h(x): return ((x * x) >> (w - k)) & mask</PRE>We assume that <tt>x</tt> is an <tt>int</tt>.In Python, an <tt>int</tt> represents a 32-bit quantity.The product of two <tt>int</tt>s is at most a 64-bit quantity.The final result is obtained by shifting the product<I>w</I>-<I>k</I> bits to the right,where <I>w</I> is the number of bits in an integerand then masking to obtain the bottom <I>k</I> bits.Note, the final result is an integer between 0 and <I>M</I>-1.<P>The middle-square method does a pretty good jobwhen the integer-valued keys are equiprobable.The middle-square method also has the characteristicthat it scatters consecutive keys nicely.However, since the middle-square method only considersa subset of the bits in the middle of <IMG WIDTH=15 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline61701" SRC="img848.gif" >,keys which have a large number of leading zeroes will collide.For example, consider the following set of keys:<P> <IMG WIDTH=332 HEIGHT=20 ALIGN=BOTTOM ALT="displaymath61660" SRC="img849.gif" ><P>This set contains all keys <I>x</I> such that <IMG WIDTH=95 HEIGHT=30 ALIGN=MIDDLE ALT="tex2html_wrap_inline61705" SRC="img850.gif" >.For all of these keys <I>h</I>(<I>x</I>)=0.<P>A similar line of reasoning applies for keys whichhave a large number of trailing zeroes.Let <I>W</I> be an even power of two.Consider the set of keys<P> <IMG WIDTH=358 HEIGHT=20 ALIGN=BOTTOM ALT="displaymath61661" SRC="img851.gif" ><P>The least significant <I>w</I>/2 bits of the keys in this set are all zero.Therefore, the least significant <I>w</I> bits of of <IMG WIDTH=15 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline61701" SRC="img848.gif" > are also zeroand as a result <I>h</I>(<I>x</I>)=0 for all such keys!<P><HR><A NAME="tex2html3669" HREF="page215.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html3667" HREF="page212.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html3661" HREF="page213.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html3671" 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 + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -