page217.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 89 行
HTML
89 行
<HTML><HEAD><TITLE>Hash Function Implementations</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="tex2html3700" HREF="page218.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html3698" HREF="page205.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html3692" HREF="page216.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html3702" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H1><A NAME="SECTION008300000000000000000">Hash Function Implementations</A></H1><A NAME="sechashingimpl"> </A><P>The preceding section presents methods of hashing integer-valued keys.In reality, we cannot expect that the keys will always be integers.Depending on the application,the keys might be letters, character stringsor even more complex data structures such as <tt>Association</tt>s or <tt>Container</tt>s.<P>In general given a set of keys, <I>K</I>,and a positive constant, <I>M</I>,a hash function is a function of the form<P> <IMG WIDTH=341 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath61895" SRC="img867.gif" ><P>In practice is it convenient to implement the hash function <I>h</I>as the composition of two functions <I>f</I> and <I>g</I>.The function <I>f</I> maps keys into integers:<P> <IMG WIDTH=288 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath61896" SRC="img868.gif" ><P>where <IMG WIDTH=10 HEIGHT=11 ALIGN=BOTTOM ALT="tex2html_wrap_inline61291" SRC="img795.gif" > is the set of integers.The function <I>g</I> maps non-negative integers into <IMG WIDTH=117 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline61919" SRC="img869.gif" >:<P> <IMG WIDTH=339 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath61897" SRC="img870.gif" ><P>Given appropriate functions <I>f</I> and <I>g</I>,the hash function <I>h</I> is simply defined as the composition of those functions:<P> <IMG WIDTH=281 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath61898" SRC="img871.gif" ><P>That is, the hash value of a key <I>x</I> is given by <I>g</I>(<I>f</I>(<I>x</I>)).<P>By decomposing the function <I>h</I> in this way,we can separate the problem into two parts:The first involves finding a suitable mapping fromthe set of keys <I>K</I> to the non-negative integers.The second involves mapping non-negative integers into the interval [0,<I>M</I>-1].Ideally, the two problems would be unrelated.That is, the choice of the function <I>f</I> wouldnot depend on the choice of <I>g</I> and <em>vice versa</em>.Unfortunately, this is not always the case.However, if we are careful,we can design the functions in such a waythat <IMG WIDTH=62 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline61941" SRC="img872.gif" > is a good hash function.<P>The hashing methods discussed in the preceding sectiondeal with integer-valued keys.But this is precisely the domain of the function <I>g</I>.Consequently, we have already examined several different alternativesfor the function <I>g</I>.On the other hand,the choice of a suitable function for <I>f</I>depends on the characteristics of its domain.<P>In the following sections,we consider various different domains (sets of keys)and develop suitable hash functions for each of them.Each domain considered is implemented as a Python classthat provides a method called <tt>__hash__</tt>.The <tt>__hash__</tt> method corresponds to the function <I>f</I>which maps keys into integers.<P>The Python built-in <tt>hash</tt> functionautomatically calls the <tt>__hash__</tt> method of a class that provides one.Thus,if <tt>obj</tt> is an instance of a class that provides a <tt>__hash__</tt> method,the following Python statements are equivalent:<PRE>hash(obj)obj.__hash__()</PRE><P><BR> <HR><UL> <LI> <A NAME="tex2html3703" HREF="page218.html#SECTION008310000000000000000">Integer Keys</A><LI> <A NAME="tex2html3704" HREF="page219.html#SECTION008320000000000000000">Floating-Point Keys</A><LI> <A NAME="tex2html3705" HREF="page220.html#SECTION008330000000000000000">Character String Keys</A><LI> <A NAME="tex2html3706" HREF="page221.html#SECTION008340000000000000000">Hashing Containers</A><LI> <A NAME="tex2html3707" HREF="page222.html#SECTION008350000000000000000">Using Associations</A></UL><HR><A NAME="tex2html3700" HREF="page218.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html3698" HREF="page205.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html3692" HREF="page216.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html3702" 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 + -
显示快捷键?