📄 page221.html
字号:
<HTML><HEAD><TITLE>Hashing Containers</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="tex2html3749" HREF="page222.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html3747" HREF="page217.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html3741" HREF="page220.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html3751" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H2><A NAME="SECTION008340000000000000000">Hashing Containers</A></H2><P>As explained in Section <A HREF="page118.html#secadtscontainers"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>,a container is an object which contains other objects.In this section we show how to define a <tt>__hash__</tt> methodfor the abstract <tt>Container</tt> class definedin Program <A HREF="page119.html#progcontainera"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>-Program <A HREF="page125.html#progcontainerd"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.The method given computes a suitable hash function on any container.<P>Given a container <I>c</I> which contains <I>n</I> objects, <IMG WIDTH=13 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline62147" SRC="img916.gif" >, <IMG WIDTH=13 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline62147" SRC="img916.gif" >, ..., <IMG WIDTH=16 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline62151" SRC="img917.gif" >,we can define the hash function <I>f</I>(<I>c</I>) as follows:<P><A NAME="eqnhashingcontainer"> </A> <IMG WIDTH=500 HEIGHT=48 ALIGN=BOTTOM ALT="equation10946" SRC="img918.gif" ><P>That is, to hash a container,simply compute the sum of the hash values of the contained objects.<P>Program <A HREF="page221.html#progcontainere"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> gives the code for the <tt>__hash__</tt> method of the abstract <tt>Container</tt> class.This method implicilty uses an iteratorto enumerate all of the objects contained in the container.It calls the built-in <tt>hash</tt> function on each object in the containerand accumulates the result.Recall that the <tt>hash</tt> functioncalls an object's <tt>__hash__</tt> method.<P><P><A NAME="11100"> </A><A NAME="progcontainere"> </A> <IMG WIDTH=575 HEIGHT=180 ALIGN=BOTTOM ALT="program10957" SRC="img919.gif" ><BR><STRONG>Program:</STRONG> <tt>Container</tt> class <tt>__hash__</tt> method.<BR><P><P>Every concrete class derived from the <tt>Container</tt> classprovides an appropriate iterator implementation.However, it is <em>not</em> necessary for any derived class to redefinethe behavior of the <tt>__hash__</tt> method--the behavior inherited from the abstract <tt>Container</tt> classis completely generic and should suffice for all concrete container classes.<P>There is a slight problem with Equation <A HREF="page221.html#eqnhashingcontainer"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.Different container types that happen to contain identical objectsproduce exactly the same hash value.For example, an empty stack and an empty list both produce the same hash value.We have avoided this situation in Program <A HREF="page221.html#progcontainere"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>by adding to the sum the value obtained from hashing theclass of the container itself.<P><HR><A NAME="tex2html3749" HREF="page222.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html3747" HREF="page217.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html3741" HREF="page220.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html3751" 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 + -