📄 page211.html

📁 wqeqwvrw rkjqhwrjwq jkhrjqwhrwq jkhrwq
💻 HTML
字号:
<HTML>
<HEAD>
<TITLE>Division 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="tex2html4523" HREF="page212.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page212.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="tex2html4521" 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="tex2html4515" HREF="page210.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page210.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="tex2html4525" 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="tex2html4526" 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="SECTION009210000000000000000">Division Method</A></H2>
<P>
Perhaps the simplest of all the methods of hashing an integer <I>x</I>
is to divide <I>x</I> by <I>M</I> and then to use the remainder modulo <I>M</I>.
This is called the
<em>division method of hashing</em><A NAME=11205>&#160;</A><A NAME=11206>&#160;</A>.
In this case, the hash function is
<P> <IMG WIDTH=309 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath62232" SRC="img884.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img884.gif"  ><P>
<P>
Generally, this approach is quite good for just about any value of <I>M</I>.
However, in certain situations some extra
care is needed in the selection of a suitable value for <I>M</I>.
For example, it is often convenient to make <I>M</I> an even number.
But this means that <I>h</I>(<I>x</I>) is even if <I>x</I> is even;
and <I>h</I>(<I>x</I>) is odd if <I>x</I> is odd.
If all possible keys are equiprobable,
then this is not a problem.
However if, say, even keys are more likely than odd keys,
the function  <IMG WIDTH=116 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline62256" SRC="img885.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img885.gif"  > will not spread the hashed
values of those keys evenly.
<P>
Similarly, it is often tempting to let <I>M</I> be a power of two.
E.g.,  <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 integer <I>k</I><I>&gt;</I>1.
In this case,
the hash function  <IMG WIDTH=114 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline62264" SRC="img887.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img887.gif"  > simply extracts the bottom <I>k</I>
bits of the binary representation of <I>x</I>.
While this hash function is quite easy to compute,
it is not a desirable function because it does not depend
on all the bits in the binary representation of <I>x</I>.
<P>
For these reasons <I>M</I> is often chosen to be a prime number.
For example, suppose there is a bias in the way the keys are created
that makes it more likely for a key to be a multiple of some small constant,
say two or three.
Then making <I>M</I> a prime increases the likelihood
that those keys are spread out evenly.
Also, if <I>M</I> is a prime number,
the division of <I>x</I> by that prime number depends on all the bits of <I>x</I>,
not just the bottom <I>k</I> bits,
for some small constant <I>k</I>.
<P>
The division method is extremely simple to implement.
The following C++ code illustrates how to do it:
<PRE>unsigned int const M = 1031; // a prime

unsigned int h (unsigned int x)
    { return x % M; }</PRE>
In this case, <tt>M</tt> is a constant.
However, an advantage of the division method is that <tt>M</tt>
need not be a compile-time constant--its value can be determined at run time.
In any event,
the running time of this implementation is clearly a constant.
<P>
A potential disadvantage of the division method
is due to the property that consecutive keys
map to consecutive hash values:
<P> <IMG WIDTH=500 HEIGHT=94 ALIGN=BOTTOM ALT="eqnarray11209" SRC="img888.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img888.gif"  ><P>
While this ensures that consecutive keys do not collide,
it does mean that consecutive array locations will be occupied.
We will see that in certain implementations this can lead
to degradation in performance.
In the following sections we consider hashing methods that
tend to scatter consecutive keys.
<P>
<HR><A NAME="tex2html4523" HREF="page212.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page212.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="tex2html4521" 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="tex2html4515" HREF="page210.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page210.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="tex2html4525" 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="tex2html4526" 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 &#169; 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 + -