page220.html

来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 222 行 · 第 1/2 页

<P>
Of the 128 characters in the 7-bit ASCII character set,
only 97 characters are printing characters
including the space, tab, and newline characters
(see Appendix&nbsp;<A HREF="page609.html#appcharcode"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>).
The remaining characters are control characters which,
depending on the application,
rarely occur in strings.
Furthermore, if we assume that letters and digits
are the most common characters in strings,
then only 62 of the 128 ASCII codes are used frequently.
Notice, the letters (both upper and lower case)
all fall between  <IMG WIDTH=39 HEIGHT=20 ALIGN=MIDDLE ALT="tex2html_wrap_inline62119" SRC="img909.gif"  > and  <IMG WIDTH=38 HEIGHT=20 ALIGN=MIDDLE ALT="tex2html_wrap_inline62121" SRC="img910.gif"  >.
All the information is in the least significant six bits.
Similarly, the digits fall between  <IMG WIDTH=31 HEIGHT=20 ALIGN=MIDDLE ALT="tex2html_wrap_inline62123" SRC="img911.gif"  > and  <IMG WIDTH=30 HEIGHT=20 ALIGN=MIDDLE ALT="tex2html_wrap_inline62125" SRC="img912.gif"  >--these differ in the least significant four bits.
These observations suggest that using  <IMG WIDTH=49 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline62127" SRC="img913.gif"  > should work well.
That is, for  <IMG WIDTH=60 HEIGHT=15 ALIGN=BOTTOM ALT="tex2html_wrap_inline61675" SRC="img845.gif"  >, the hash value depends on the last five characters
plus two bits of the sixth-last character.
<P>
We have developed a hashing scheme which works quite well
given strings which differ in the trailing letters.
For example, the strings <tt>&quot;temp1&quot;</tt>, <tt>&quot;temp2&quot;</tt>, and <tt>&quot;temp3&quot;</tt>,
all produce different hash values.
However, in certain applications the strings differ in the leading letters.
For example, the two <em>Internet domain names</em><A NAME=10877>&#160;</A>
<tt>&quot;ece.uwaterloo.ca&quot;</tt> and <tt>&quot;cs.uwaterloo.ca&quot;</tt> collide
when using Equation&nbsp;<A HREF="page220.html#eqnhashingstring3"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.
Essentially, the effect of the characters that differ is lost
because the corresponding bits have been shifted out of the hash value.
<P>
<P><A NAME="11097">&#160;</A><A NAME="progstrnga">&#160;</A> <IMG WIDTH=575 HEIGHT=275 ALIGN=BOTTOM ALT="program10881" SRC="img914.gif"  ><BR>
<STRONG>Program:</STRONG> <tt>String</tt> class <tt>__hash__</tt> method.<BR>
<P>
<P>
This suggests a final modification
which shown in Program&nbsp;<A HREF="page220.html#progstrnga"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.
Instead of losing the <I>b</I>=6 most significant bits
when the variable <tt>result</tt> is shifted left,
we retain those bits and <em>exclusive or</em><A NAME=10893>&#160;</A> them back into
the shifted <tt>result</tt> variable.
Using this approach,
the two strings <tt>&quot;ece.uwaterloo.ca&quot;</tt> and <tt>&quot;cs.uwaterloo.ca&quot;</tt>
produce different hash values.
<P>
Table&nbsp;<A HREF="page220.html#tblhashingwords"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> lists a number of different
character strings together with the hash values obtained
using Program&nbsp;<A HREF="page220.html#progstrnga"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.
For example, to hash the string <tt>&quot;fyra&quot;</tt>,
the following computation is performed
(all numbers in octal):
<DIV ALIGN=CENTER><P ALIGN=CENTER><TABLE COLS=11 BORDER RULES=GROUPS>
<COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER>
<TBODY>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>
            </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>1</TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>4</TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>6</TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP><code>f</code></TD></TR>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 
     <IMG WIDTH=11 HEIGHT=18 ALIGN=MIDDLE ALT="tex2html_wrap_inline62133" SRC="img915.gif"  ></TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>1</TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>7</TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>1</TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP><code>y</code></TD></TR>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 
     <IMG WIDTH=11 HEIGHT=18 ALIGN=MIDDLE ALT="tex2html_wrap_inline62133" SRC="img915.gif"  ></TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>1</TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>6</TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>2</TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP><code>r</code></TD></TR>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 
     <IMG WIDTH=11 HEIGHT=18 ALIGN=MIDDLE ALT="tex2html_wrap_inline62133" SRC="img915.gif"  ></TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>1</TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>4</TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>1</TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP><code>a</code></TD></TR>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>
<P>
            </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>1</TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>4</TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>7</TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>7</TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>0</TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>6</TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>3</TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>4</TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>1</TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP></TD></TR>
</TBODY>
</TABLE>
</P></DIV>
<P>
<P><A NAME="11099">&#160;</A>
<P>
    <A NAME="tblhashingwords">&#160;</A>
    <DIV ALIGN=CENTER><P ALIGN=CENTER><TABLE COLS=2 BORDER FRAME=HSIDES RULES=GROUPS>
<COL ALIGN=LEFT><COL ALIGN=RIGHT>
<TBODY>
<TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP>
	    <I>x</I> </TD><TD VALIGN=BASELINE ALIGN=RIGHT NOWRAP> <tt>Hash(<I>x</I>)</tt> (octal) </TD></TR>
</TBODY><TBODY>
<TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP><tt>&quot;ett&quot;</tt> </TD><TD VALIGN=BASELINE ALIGN=RIGHT NOWRAP> <tt>01446564</tt> </TD></TR>
<TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> 
	    <tt>&quot;tv&#229;&quot;</tt> </TD><TD VALIGN=BASELINE ALIGN=RIGHT NOWRAP> <tt>05360614565</tt> </TD></TR>
<TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> 
	    <tt>&quot;tre&quot;</tt> </TD><TD VALIGN=BASELINE ALIGN=RIGHT NOWRAP> <tt>01656345</tt> </TD></TR>
<TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> 
	    <tt>&quot;fyra&quot;</tt> </TD><TD VALIGN=BASELINE ALIGN=RIGHT NOWRAP> <tt>0147706341</tt> </TD></TR>
<TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> 
	    <tt>&quot;fem&quot;</tt> </TD><TD VALIGN=BASELINE ALIGN=RIGHT NOWRAP> <tt>01474455</tt> </TD></TR>
<TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> 
	    <tt>&quot;sex&quot;</tt> </TD><TD VALIGN=BASELINE ALIGN=RIGHT NOWRAP> <tt>01624470</tt> </TD></TR>
<TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> 
	    <tt>&quot;sju&quot;</tt> </TD><TD VALIGN=BASELINE ALIGN=RIGHT NOWRAP> <tt>01625365</tt> </TD></TR>
<TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> 
	    <tt>&quot;&#229;tta&quot;</tt> </TD><TD VALIGN=BASELINE ALIGN=RIGHT NOWRAP> <tt>01564656541</tt> </TD></TR>
<TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> 
	    <tt>&quot;nio&quot;</tt> </TD><TD VALIGN=BASELINE ALIGN=RIGHT NOWRAP> <tt>01575057</tt> </TD></TR>
<TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> 
	    <tt>&quot;tio&quot;</tt> </TD><TD VALIGN=BASELINE ALIGN=RIGHT NOWRAP> <tt>01655057</tt> </TD></TR>
<TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> 
	    <tt>&quot;elva&quot;</tt> </TD><TD VALIGN=BASELINE ALIGN=RIGHT NOWRAP> <tt>0144556741</tt> </TD></TR>
<TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> 
	    <tt>&quot;tolv&quot;</tt> </TD><TD VALIGN=BASELINE ALIGN=RIGHT NOWRAP> <tt>0165565566</tt> </TD></TR>
</TBODY>
<CAPTION ALIGN=BOTTOM><STRONG>Table:</STRONG> Sample character string keys and the hash values obtained using
	Program&nbsp;<A HREF="page220.html#progstrnga"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.</CAPTION></TABLE>
</P></DIV><P><HR><A NAME="tex2html3738" HREF="page221.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html3736" HREF="page217.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html3730" HREF="page219.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A>  <A NAME="tex2html3740" 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 &#169; 2003</a> by <a href="../signature.html">Bruno R. Preiss, P.Eng.</a>  All rights reserved.

</ADDRESS>
</BODY>
</HTML>