page213.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 82 行
HTML
82 行
<HTML><HEAD><TITLE>Division 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="tex2html3658" HREF="page214.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html3656" HREF="page212.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html3650" HREF="page212.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html3660" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H2><A NAME="SECTION008210000000000000000">Division Method</A></H2><A NAME="sechashingdivision"> </A><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=10611> </A><A NAME=10612> </A>.In this case, the hash function is<P> <IMG WIDTH=314 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath61605" SRC="img839.gif" ><P><P>Generally, this approach is quite good for just about any value of <I>M</I>.However, in certain situations some extracare 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_inline61629" SRC="img840.gif" > will not spread the hashedvalues of those keys evenly.<P>Similarly, it is often tempting to let <I>M</I> be a power of two.For example, <IMG WIDTH=52 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline61633" SRC="img841.gif" > for some integer <I>k</I><I>></I>1.In this case,the hash function <IMG WIDTH=113 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline61637" SRC="img842.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 dependon 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 createdthat 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 likelihoodthat 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 Python code illustrates how to do it:<PRE>M = 1021 # a primedef h(x): return abs(x) % M</PRE>In this case, it appears that <tt>M</tt> has a constant value.However, an advantage of the division method is thatthe value of <tt>M</tt> need not be static--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 methodis due to the property that consecutive keysmap to consecutive hash values:<P> <IMG WIDTH=500 HEIGHT=94 ALIGN=BOTTOM ALT="eqnarray10615" SRC="img843.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 leadto degradation in performance.In the following sections we consider hashing methods thattend to scatter consecutive keys.<P><HR><A NAME="tex2html3658" HREF="page214.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html3656" HREF="page212.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html3650" HREF="page212.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html3660" 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 + -
显示快捷键?