page205.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 68 行
HTML
68 行
<HTML><HEAD><TITLE>Hashing, Hash Tables, and Scatter 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="tex2html3558" HREF="page206.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html3556" HREF="book.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html3550" HREF="page204.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html3560" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H1><A NAME="SECTION008000000000000000000">Hashing, Hash Tables, and Scatter Tables</A></H1><P><A NAME="chaphashing"> </A><P>A very common paradigm in data processinginvolves storing information in a tableand 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 Python compiler.The compiler uses a <em>symbol table</em><A NAME=10534> </A>to keep track of the user-defined symbols in a Python program.As it compiles a program,the compiler inserts an entry in the symbol tableevery time a new symbol is declared.In addition,every time a symbol is used,the compiler looks up the attributes associated with that symbolto see that it is being used correctlyand to guide the generation of the Python byte 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 numberand 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 insertionand/or look-up operations.Occasionally it is also necessary to remove items from the database.Because a large number of operations will be donewe want to do them as quickly as possible.<P><BR> <HR><UL> <LI> <A NAME="tex2html3561" HREF="page206.html#SECTION008100000000000000000">Hashing-The Basic Idea</A><LI> <A NAME="tex2html3562" HREF="page212.html#SECTION008200000000000000000">Hashing Methods</A><LI> <A NAME="tex2html3563" HREF="page217.html#SECTION008300000000000000000">Hash Function Implementations</A><LI> <A NAME="tex2html3564" HREF="page223.html#SECTION008400000000000000000">Hash Tables</A><LI> <A NAME="tex2html3565" HREF="page230.html#SECTION008500000000000000000">Scatter Tables</A><LI> <A NAME="tex2html3566" HREF="page238.html#SECTION008600000000000000000">Scatter Table using Open Addressing</A><LI> <A NAME="tex2html3567" HREF="page248.html#SECTION008700000000000000000">Applications</A><LI> <A NAME="tex2html3568" HREF="page249.html#SECTION008800000000000000000">Exercises</A><LI> <A NAME="tex2html3569" HREF="page250.html#SECTION008900000000000000000">Projects</A></UL><HR><A NAME="tex2html3558" HREF="page206.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html3556" HREF="book.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html3550" HREF="page204.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html3560" 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 + -
显示快捷键?