📄 page248.html
字号:
<HTML><HEAD><TITLE>Applications</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="tex2html4054" HREF="page249.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html4052" HREF="page205.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html4046" HREF="page247.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html4056" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H1><A NAME="SECTION008700000000000000000">Applications</A></H1><P>Hash and Scatter tables have many applications.The principal characteristic of such applicationsis that keyed information needs to be frequently accessedand the access pattern is either unknown or known to be random.For example, hash tables are often used to implement the<em>symbol table</em><A NAME=13891> </A> of a programming language compiler.A symbol table is used to keep track of information associatedwith the symbols (variable and method names) used by a programmer.In this case,the keys are character strings and each key hash associatedwith it some information about the symbol(e.g., type, address, value, lifetime, scope).<P>This section presents a simple application of hash and scatter tables.Suppose we are required to count the number of occurrences ofeach distinct word contained in a text file.We can do this easily using a hash or scatter table.Program <A HREF="page248.html#progalgorithmsk"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> gives the an implementation.<P><P><A NAME="13896"> </A><A NAME="progalgorithmsk"> </A> <IMG WIDTH=575 HEIGHT=525 ALIGN=BOTTOM ALT="program13893" SRC="img1029.gif" ><BR><STRONG>Program:</STRONG> Hash/scatter table application--counting words.<BR><P><P>The nested class <tt>Counter</tt>is used to count the number of occurrences of a word.The <tt>Counter</tt> class provides an <tt>increment</tt> methodthat is called to increase the value of the counter by one.<P>The <tt>wordCounter</tt> methoddoes the actual work of counting the words in the input file.The local variable <tt>table</tt> refers to a <tt>ChainedHashTable</tt>that is used to keep track of the words and counts.The objects which are put into the hash tableare all instances of the class <tt>Association</tt>.Each association has as its key a <tt>str</tt> class instance,and as its value a <tt>Counter</tt> class instance.<P>The main loop of the <tt>wordCounter</tt> method reads a line of textfrom the input stream.Each line of text is split into an array of wordsand the inner loop processes each word one at a time.For each word,a <tt>find</tt> operation is done on the hash table to determineif there is already an association for the given key.If none is found,a new association is created an inserted into the hash table.The given word is used as the key of the new associationand the value is a counter which is initialized to one.On the other hand,if there is already an association for the given word in the hash table,the corresponding counter is incremented.When the <tt>wordCounter</tt> method reaches the end of the input stream,it simply prints the hash table on the given output stream.<P>The running time of the <tt>wordCounter</tt> methoddepends on a number of factors,including the number of different keys,the frequency of occurrence of each key,and the distribution of the keys in the overall space of keys.Of course, the hash/scatter table implementation chosenhas an effect as does the size of the table used.For a reasonable set of keys we expect the hash functionto do a good job of spreading the keys uniformly in the table.Provided a sufficiently large table is used,the average search and insertion time is bounded by a constant.Under these ideal conditions the running time should be <I>O</I>(<I>n</I>),where <I>n</I> is the number of words in the input file.<P><HR><A NAME="tex2html4054" HREF="page249.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html4052" HREF="page205.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html4046" HREF="page247.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html4056" 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 + -