page206.html

来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 82 行

HTML
82 行
字号 
<HTML><HEAD><TITLE>Hashing-The Basic Idea</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="tex2html3578" HREF="page207.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html3576" HREF="page205.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html3570" HREF="page205.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A>  <A NAME="tex2html3580" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H1><A NAME="SECTION008100000000000000000">Hashing-The Basic Idea</A></H1><P>In this chapter we examine data structures which aredesigned specifically with the objective ofproviding efficient insertion and find operations.In order to meet the design objective,certain concessions are made.Specifically, we do not require that there be anyspecific ordering of the items in the container.In addition,while we still require the ability to remove items from the container,it is not our primary objective to make removal as efficientas the insertion and find operations.<P>Ideally we would build a data structure for whichboth the insertion and find operations are <I>O</I>(1) in the worst case.However, this kind of performance can only be achievedwith complete <em>a priori</em> knowledge.We need to know beforehand specifically which items are to be insertedinto the container.Unfortunately, we do not have this information in the general case.So, if we cannot guarantee <I>O</I>(1) performance in the <em>worst case</em>,then we make it our design objective to achieve <I>O</I>(1)performance <em>in the average case</em>.<P>The constant time performance objective immediately leads usto the following conclusion:Our implementation must be based in some way on an arrayrather than a linked list.This is because we can access the  <IMG WIDTH=20 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline61477" SRC="img821.gif"  > element of an array in constant time,whereas the same operation in a linked list takes <I>O</I>(<I>k</I>) time.<P>In the previous chapter,we consider two searchable containers--the <em>ordered list</em> and the <em>sorted list</em>.In the case of an ordered list,the cost of an insertion is <I>O</I>(1)and the cost of the find operation is <I>O</I>(<I>n</I>).For a sorted list the cost of insertion is <I>O</I>(<I>n</I>)and the cost of the find operation is  <IMG WIDTH=56 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59347" SRC="img400.gif"  > for the array implementation.<P>Clearly, neither the ordered list nor the sorted listmeets our performance objectives.The essential problem is that a search,either linear or binary,is always necessary.In the ordered list,the find operation uses a linear search to locate the item.In the sorted list,a binary search can be used to locate the itembecause the data is sorted.However, in order to keep the data sorted,insertion becomes <I>O</I>(<I>n</I>).<P>In order to meet the performance objectiveof constant time insert and find operations,we need a way to do them <em>without performing a search</em>.That is, given an item <I>x</I>,we need to be able to determine directly from <I>x</I>the array position where it is to be stored.<P><BR> <HR><UL> <LI> <A NAME="tex2html3581" HREF="page207.html#SECTION008100100000000000000">Example</A><LI> <A NAME="tex2html3582" HREF="page208.html#SECTION008110000000000000000">Keys and Hash Functions</A></UL><HR><A NAME="tex2html3578" HREF="page207.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html3576" HREF="page205.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html3570" HREF="page205.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A>  <A NAME="tex2html3580" 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 &#169; 2003</a> by <a href="../signature.html">Bruno R. Preiss, P.Eng.</a>  All rights reserved.</ADDRESS></BODY></HTML>

page206.html - 源码说明

本页面展示了「Data Structures And Algorithms With Object-Oriented Design Patterns In Python (2003) source code and」中的 page206.html 源码文件，采用 HTML 编程语言编写，共 82 行代码。您可以在线阅读完整代码内容，也可以返回资源详情页下载完整源码包进行本地学习和开发。

虫虫下载站收录了大量与Object-Oriented相关的技术资源，包括源代码、技术文档、电路图等，是电子工程师和嵌入式开发者的专业学习平台。

⌨️ 快捷键说明

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