page223.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 77 行
HTML
77 行
<HTML><HEAD><TITLE>Hash Tables</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="tex2html3769" HREF="page224.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html3767" HREF="page205.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html3761" HREF="page222.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html3771" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H1><A NAME="SECTION008400000000000000000">Hash Tables</A></H1><P>A <em>hash table</em><A NAME=10992> </A> is a searchable container.As such, it provides methodsfor putting an object into the container,finding an object in the container,and removing an object from the container.<P>Program <A HREF="page223.html#proghashTablea"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> introduces the <tt>HashTable</tt> class.The abstract <tt>HashTable</tt> class extendsthe the abstract <tt>SearchableContainer</tt> classdefined in Program <A HREF="page126.html#progsearchableContainera"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.<P><P><A NAME="11104"> </A><A NAME="proghashTablea"> </A> <IMG WIDTH=575 HEIGHT=313 ALIGN=BOTTOM ALT="program10998" SRC="img924.gif" ><BR><STRONG>Program:</STRONG> Abstract <tt>HashTable</tt> class.<BR><P><P>Program <A HREF="page223.html#proghashTablea"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> declares the <tt>__len__</tt> method to be an abstract method.Concrete classes derived from <tt>HashTable</tt> must override this method.Program <A HREF="page223.html#proghashTablea"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> also defines the property called <tt>loadFactor</tt>.The purpose of this property is explained in Section <A HREF="page229.html#sechashingloadfactor"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.<P>Program <A HREF="page223.html#proghashTableb"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> continues the definitionof the <tt>HashTable</tt> class.Three methods, <tt>f</tt>, <tt>g</tt> and <tt>h</tt>, are defined.<P><P><A NAME="11109"> </A><A NAME="proghashTableb"> </A> <IMG WIDTH=575 HEIGHT=237 ALIGN=BOTTOM ALT="program11022" SRC="img925.gif" ><BR><STRONG>Program:</STRONG> Abstract <tt>HashTable</tt> class <tt>f</tt>, <tt>g</tt> and <tt>h</tt> methods.<BR><P><P>The methods <tt>f</tt>, <tt>g</tt>, and <tt>h</tt>correspond to the composition <IMG WIDTH=62 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline61941" SRC="img872.gif" >discussed in Section <A HREF="page217.html#sechashingimpl"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.The <tt>f</tt> methodtakes as an object and calls the built-in <tt>hash</tt> function on thatobject to compute an integer.The <tt>g</tt> method uses the <em>division method</em> of hashingdefined in Section <A HREF="page213.html#sechashingdivision"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>to map an integer into the interval [0,<I>M</I>-1],where <I>M</I> is the length of the hash table.Finally, the <tt>h</tt> method computes the composition of <tt>f</tt> and <tt>g</tt>.<P>Figure <A HREF="page223.html#figclasses4"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> shows the class hierarchyfor the classes discussed in this chapter.These classes illustrate various ways of implementing hash tables.In all cases,the underlying implementation of the hash table makes use of an array.The position of an object in the array is determined by hashing the object.The main problem to be resolved is how to deal with collisions--two different objects cannot occupy the same array position at the same time.In the next section,we consider an approach which solves the problem of collisionsby keeping objects that collide in a linked list.<P><P><A NAME="11054"> </A><A NAME="figclasses4"> </A> <IMG WIDTH=575 HEIGHT=246 ALIGN=BOTTOM ALT="figure11050" SRC="img926.gif" ><BR><STRONG>Figure:</STRONG> Object class hierarchy.<BR><P><BR> <HR><UL> <LI> <A NAME="tex2html3772" HREF="page224.html#SECTION008410000000000000000">Separate Chaining</A><LI> <A NAME="tex2html3773" HREF="page229.html#SECTION008420000000000000000">Average Case Analysis</A></UL><HR><A NAME="tex2html3769" HREF="page224.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html3767" HREF="page205.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html3761" HREF="page222.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html3771" 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 + -
显示快捷键?