📄 page241.html
字号:
<HTML><HEAD><TITLE>Double Hashing</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="tex2html3977" HREF="page242.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html3975" HREF="page238.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html3969" HREF="page240.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html3979" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H2><A NAME="SECTION008630000000000000000">Double Hashing</A></H2><P>While quadratic probing does indeed eliminate the primary clustering problem,it places a restriction on the number of items that can be put in the table--the table must be less than half full.<em>Double Hashing</em><A NAME=13260> </A>is yet another method of generating a probing sequence.It requires two distinct hash functions,<P> <IMG WIDTH=187 HEIGHT=40 ALIGN=BOTTOM ALT="gather13261" SRC="img998.gif" ><P>The probing sequence is then computed as follows<P> <IMG WIDTH=359 HEIGHT=17 ALIGN=BOTTOM ALT="displaymath62487" SRC="img999.gif" ><P>That is, the scatter tables is searched as follows:<P> <IMG WIDTH=500 HEIGHT=118 ALIGN=BOTTOM ALT="eqnarray13263" SRC="img1000.gif" ><P><P>Since the collision resolution function is <I>c</I>(<I>i</I>)=<I>ih</I>'(<I>x</I>),the probe sequence depends on the key as follows:If <I>h</I>'(<I>x</I>)=1, then the probing sequence for the key <I>x</I>is the same as linear probing.If <I>h</I>'(<I>x</I>)=2, the probing sequence examines every other array position.This works as long as <I>M</I> is not even.<P>Clearly since <I>c</I>(0)=0,the double hashing method satisfies property 1.Furthermore, property 2 is satisfiedas long as <I>h</I>'(<I>x</I>) and <I>M</I> are relatively prime.Since <I>h</I>'(<I>x</I>) can take on any value between 1 and <I>M</I>-1,<I>M</I> must be a prime number.<P>But what is a suitable choice for the function <I>h</I>'?Recall that <I>h</I> is defined as the composition of two functions, <IMG WIDTH=62 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline61941" SRC="img872.gif" > where <IMG WIDTH=116 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline62055" SRC="img898.gif" >.We can define <I>h</I>' as the composition <IMG WIDTH=37 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline62523" SRC="img1001.gif" >,where<P><A NAME="eqnhashingdouble"> </A> <IMG WIDTH=500 HEIGHT=17 ALIGN=BOTTOM ALT="equation13265" SRC="img1002.gif" ><P><P>Double hashing reduces the occurrence of primary clusteringsince it only does a linear search if <I>h</I>'(<I>x</I>) hashes to the value 1.For a good hash function,this should only happen with probability 1/(<I>M</I>-1).However, for double hashing to work at all,the size of the scatter table, <I>M</I>, must be a prime number.Table <A HREF="page241.html#tblhashingprobing"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> summarizesthe characteristics of the various open addressing probing sequences.<P><P><A NAME="13270"> </A><P> <A NAME="tblhashingprobing"> </A> <DIV ALIGN=CENTER><P ALIGN=CENTER><TABLE COLS=4 BORDER FRAME=HSIDES RULES=GROUPS><COL ALIGN=LEFT><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><TBODY><TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> probing sequence </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> primary clustering </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> capacity limit </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> size restriction </TD></TR></TBODY><TBODY><TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP>linear probing </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> yes </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> none </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> none </TD></TR><TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> quadratic probing </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> no </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=38 HEIGHT=29 ALIGN=MIDDLE ALT="tex2html_wrap_inline62485" SRC="img996.gif" > </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>M</I> must be prime </TD></TR><TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> double hashing </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> no </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> none </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>M</I> must be prime </TD></TR></TBODY><CAPTION ALIGN=BOTTOM><STRONG>Table:</STRONG> Characteristics of the open addressing probing sequences.</CAPTION></TABLE></P></DIV><P><HR><A NAME="tex2html3977" HREF="page242.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html3975" HREF="page238.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html3969" HREF="page240.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html3979" 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 + -