page215.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 68 行
HTML
68 行
<HTML><HEAD><TITLE>Multiplication 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="tex2html3680" HREF="page216.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html3678" HREF="page212.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html3672" HREF="page214.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html3682" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H2><A NAME="SECTION008230000000000000000">Multiplication Method</A></H2><P>A very simple variation on the middle-square method thatalleviates its deficiencies is the so-called,<em>multiplication hashing method</em><A NAME=10635> </A><A NAME=10636> </A>.Instead of multiplying the key <I>x</I> by itself,we multiply the key by a carefully chosen constant <I>a</I>,and then extract the middle <I>k</I> bits from the result.In this case,the hashing function is<P> <IMG WIDTH=342 HEIGHT=39 ALIGN=BOTTOM ALT="displaymath61719" SRC="img852.gif" ><P><P>What is a suitable choice for the constant <I>a</I>?If we want to avoid the problems that the middle-square methodencounters with keys having a large number of leading or trailing zeroes,then we should choose an <I>a</I> that has neitherleading nor trailing zeroes.<P>Furthermore, if we choose an <I>a</I> that is<em>relatively prime</em><A NAME="tex2html357" HREF="footnode.html#10686"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/foot_motif.gif"></A>to <I>W</I>,then there exists another number <I>a</I>' such that <IMG WIDTH=122 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline61747" SRC="img853.gif" >.In other words, <I>a</I>' is the <em>inverse</em><A NAME=10644> </A>of <I>a</I> modulo <I>W</I>,since the product of <I>a</I> and its inverse is one.Such a number has the nice property that if we take a key <I>x</I>,and multiply it by <I>a</I> to get <I>ax</I>,we can recover the original key by multiplying the product again by <I>a</I>',since <I>axa</I>'=<I>aa</I>'<I>x</I>=1<I>x</I>.<P>There are many possible constants which the desired properties.One possibility which is suited for 32-bit arithmetic (i.e., <IMG WIDTH=60 HEIGHT=15 ALIGN=BOTTOM ALT="tex2html_wrap_inline61675" SRC="img845.gif" >)is <IMG WIDTH=118 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline61771" SRC="img854.gif" >.The binary representation of <I>a</I> is<P> <IMG WIDTH=392 HEIGHT=12 ALIGN=BOTTOM ALT="displaymath61720" SRC="img855.gif" ><P>This number has neither many leading nor trailing zeroes.Also, this value of <I>a</I> and <IMG WIDTH=60 HEIGHT=15 ALIGN=BOTTOM ALT="tex2html_wrap_inline61675" SRC="img845.gif" > are relatively primeand the inverse of <I>a</I> modulo <I>W</I> is <IMG WIDTH=111 HEIGHT=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline61783" SRC="img856.gif" >.<P>The following code fragment illustratesthe multiplication method of hashing:<PRE>k = 10 # M==1024w = 32mask = (1 << k) - 1a = 2654435769Ldef h(x): return ((x * a) >> (w - k)) & mask</PRE>The code is a simple modification of the middle-square version.Nevertheless, the running time remains <I>O</I>(1).<P><HR><A NAME="tex2html3680" HREF="page216.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html3678" HREF="page212.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html3672" HREF="page214.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html3682" 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 + -
显示快捷键?