📄 page203.html

📁 wqeqwvrw rkjqhwrjwq jkhrjqwhrwq jkhrwq
💻 HTML
字号:
<HTML>
<HEAD>
<TITLE>Hashing, Hash Tables and Scatter Tables</TITLE>
</HEAD>
<BODY bgcolor="#FFFFFF">
 <img src="cover75.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cover75.gif" alt="Logo" align=right>
<b>Data Structures and Algorithms 
with Object-Oriented Design Patterns in C++</b><br>
<A NAME="tex2html4415" HREF="page204.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page204.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="next_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/next_motif.gif"></A> <A NAME="tex2html4413" HREF="book.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/book.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="up_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/up_motif.gif"></A> <A NAME="tex2html4407" HREF="page202.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page202.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="previous_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/previous_motif.gif"></A> <A NAME="tex2html4417" HREF="page9.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page9.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="contents_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/contents_motif.gif"></A> <A NAME="tex2html4418" HREF="page620.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page620.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="index_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/index_motif.gif"></A> <BR><HR>
<H1><A NAME="SECTION009000000000000000000">Hashing, Hash Tables and Scatter Tables</A></H1>
<P>
<A NAME="chaphashing">&#160;</A>
<P>
A very common paradigm in data processing
involves storing information in a table
and then later retrieving the information stored there.
For example,
consider a database of driver's license records.
The database contains one record for each driver's license issued.
Given a driver's license number,
we can look up the information associated with that number.
<P>
Similar operations are done by the C++ compiler.
The compiler uses a <em>symbol table</em><A NAME=11132>&#160;</A>
to keep track of the user-defined symbols in a C++ program.
As it compiles a program,
the compiler inserts an entry in the symbol table
every time a new symbol is declared.
In addition,
every time a symbol is used,
the compiler looks up the attributes associated with that symbol
to see that it is being used correctly
and to guide the generation of the executable code.
<P>
Typically the database comprises a collection of key-and-value pairs.
Information is retrieved from the database by searching for a given key.
In the case of the driver's license database,
the key is the driver's license number
and in the case of the symbol table,
the key is the name of the symbol.
<P>
In general,
an application may perform a large number of insertion
and/or look-up operations.
Occasionally it is also necessary to remove items from the database.
Because a large number of operations will be done
we want to do them as quickly as possible.
<P>
<BR> <HR>
<UL> 
<LI> <A NAME="tex2html4419" HREF="page204.html#SECTION009100000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page204.html#SECTION009100000000000000000">Hashing-The Basic Idea</A>
<LI> <A NAME="tex2html4420" HREF="page210.html#SECTION009200000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page210.html#SECTION009200000000000000000">Hashing Methods</A>
<LI> <A NAME="tex2html4421" HREF="page215.html#SECTION009300000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page215.html#SECTION009300000000000000000">Hash Function Implementations</A>
<LI> <A NAME="tex2html4422" HREF="page222.html#SECTION009400000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page222.html#SECTION009400000000000000000">Hash Tables</A>
<LI> <A NAME="tex2html4423" HREF="page229.html#SECTION009500000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page229.html#SECTION009500000000000000000">Scatter Tables</A>
<LI> <A NAME="tex2html4424" HREF="page237.html#SECTION009600000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page237.html#SECTION009600000000000000000">Scatter Table using Open Addressing</A>
<LI> <A NAME="tex2html4425" HREF="page247.html#SECTION009700000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page247.html#SECTION009700000000000000000">Applications</A>
<LI> <A NAME="tex2html4426" HREF="page248.html#SECTION009800000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page248.html#SECTION009800000000000000000">Exercises</A>
<LI> <A NAME="tex2html4427" HREF="page249.html#SECTION009900000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page249.html#SECTION009900000000000000000">Projects</A>
</UL>
<HR><A NAME="tex2html4415" HREF="page204.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page204.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="next_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/next_motif.gif"></A> <A NAME="tex2html4413" HREF="book.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/book.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="up_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/up_motif.gif"></A> <A NAME="tex2html4407" HREF="page202.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page202.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="previous_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/previous_motif.gif"></A> <A NAME="tex2html4417" HREF="page9.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page9.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="contents_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/contents_motif.gif"></A> <A NAME="tex2html4418" HREF="page620.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page620.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="index_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/index_motif.gif"></A> <P><ADDRESS>
<img src="bruno.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/bruno.gif" alt="Bruno" align=right>
<a href="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html  \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address.  \n\nDo you want to open it from the server?'))window.location='http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html">Copyright &#169; 1997</a> by <a href="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html  \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address.  \n\nDo you want to open it from the server?'))window.location='http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html">Bruno R. Preiss, P.Eng.</a>  All rights reserved.

</ADDRESS>
</BODY>
</HTML>
⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -