page212.html
来自「wqeqwvrw rkjqhwrjwq jkhrjqwhrwq jkhrwq」· HTML 代码 · 共 83 行
HTML
83 行
<HTML>
<HEAD>
<TITLE>Middle Square Method</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="tex2html4535" HREF="page213.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page213.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="tex2html4533" HREF="page210.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page210.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="tex2html4527" HREF="page211.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page211.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="tex2html4537" 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="tex2html4538" 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="SECTION009220000000000000000">Middle Square Method</A></H2>
<P>
In this section we consider a hashing method
which avoids the use of division.
Since integer division is usually slower than integer multiplication,
by avoiding division we can potentially improve
the running time of the hashing algorithm.
We can avoid division by making use of the fact that
a computer does finite-precision integer arithmetic.
E.g., all arithmetic is done modulo <I>W</I>
where <IMG WIDTH=54 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline62294" SRC="img889.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img889.gif" > is a power of two such that
<I>w</I> is the <em>word size</em><A NAME=11213> </A> of the computer.
<P>
The <em>middle-square hashing method</em><A NAME=11215> </A><A NAME=11216> </A>
works as follows.
First, we assume that <I>M</I> is a power of two,
say <IMG WIDTH=51 HEIGHT=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline62260" SRC="img886.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img886.gif" > for some <IMG WIDTH=36 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline59577" SRC="img356.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img356.gif" >.
Then, to hash an integer <I>x</I>,
we use the following hash function:
<P> <IMG WIDTH=342 HEIGHT=38 ALIGN=BOTTOM ALT="displaymath62286" SRC="img890.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img890.gif" ><P>
<P>
Notice that since <I>M</I> and <I>W</I> are both powers of two,
the ratio <IMG WIDTH=94 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline62310" SRC="img891.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img891.gif" > is also a power two.
Therefore, in order to multiply the term <IMG WIDTH=83 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline62312" SRC="img892.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img892.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 illustrates
the middle-square method of hashing:
<PRE>unsigned int const k = 10; // M==1024
unsigned int const w = bitsizeof (unsigned int);
unsigned int h (unsigned int x)
{ return (x * x) >> (w - k); }</PRE>
Since <tt>x</tt> is an <tt>unsigned int</tt>,
the product <tt>x * x</tt> is also an an <tt>unsigned int</tt>.
If 32-bit integers are used,
the product is also a 32-bit integer.
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 integer.<A NAME="tex2html388" HREF="footnode.html#11298" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/footnode.html#11298"><IMG ALIGN=BOTTOM ALT="gif" SRC="foot_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/foot_motif.gif"></A><A NAME=11299> </A>
By definition, the right shift inserts zeroes on the left.
Therefore, the result always falls between 0 and <I>M</I>-1.
<P>
The middle-square method does a pretty good job
when the integer-valued keys are equiprobable.
The middle-square method also has the characteristic
that it scatters consecutive keys nicely.
However, since the middle-square method only considers
a subset of the bits in the middle of <IMG WIDTH=15 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline62328" SRC="img893.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img893.gif" >,
keys which have a large number of leading zeroes will collide.
E.g., consider the following set of keys:
<P> <IMG WIDTH=333 HEIGHT=20 ALIGN=BOTTOM ALT="displaymath62287" SRC="img894.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img894.gif" ><P>
This set contains all keys <I>x</I> such that <IMG WIDTH=87 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline62332" SRC="img895.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img895.gif" >.
For all of these keys <I>h</I>(<I>x</I>)=0.
<P>
A similar line of reasoning applies for keys which
have a large number of trailing zeroes.
Let <I>W</I> be an even power of two.
Consider the set of keys
<P> <IMG WIDTH=363 HEIGHT=20 ALIGN=BOTTOM ALT="displaymath62288" SRC="img896.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img896.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=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline62328" SRC="img893.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img893.gif" > are also zero
and as a result <I>h</I>(<I>x</I>)=0 for all such keys!
<P>
<HR><A NAME="tex2html4535" HREF="page213.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page213.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="tex2html4533" HREF="page210.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page210.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="tex2html4527" HREF="page211.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page211.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="tex2html4537" 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="tex2html4538" 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 + =
减小字号Ctrl + -
显示快捷键?