page204.html
来自「wqeqwvrw rkjqhwrjwq jkhrjqwhrwq jkhrwq」· HTML 代码 · 共 82 行
HTML
82 行
<HTML>
<HEAD>
<TITLE>Hashing-The Basic Idea</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="tex2html4436" HREF="page205.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page205.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="tex2html4434" HREF="page203.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page203.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="tex2html4428" HREF="page203.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page203.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="tex2html4438" 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="tex2html4439" 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="SECTION009100000000000000000">Hashing-The Basic Idea</A></H1>
<P>
In this chapter we examine data structures which are
designed specifically with the objective of
providing efficient insertion and find operations.
In order to meet the design objective,
certain concessions are made.
Specifically, we do not require that there be any
specific 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 efficient
as the insertion and find operations.
<P>
Ideally we would build a data structure for which
both the insertion and find operations are <I>O</I>(1) in the worst case.
However, this kind of performance can only be achieved
with complete <em>a priori</em> knowledge.
We need to know beforehand specifically which items are to be inserted
into 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 us
to the following conclusion:
Our implementation must be based in some way on an array
rather than a linked list.
This is because we can access the <IMG WIDTH=20 HEIGHT=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline61700" SRC="img803.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img803.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_inline59891" SRC="img403.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img403.gif" > for the array implementation.
<P>
Clearly, neither the ordered list nor the sorted list
meets 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 item
because 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 objective
of constant time insert and find operations,
we need a way to do them <em>without performing a search</em>.
I.e., 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="tex2html4440" HREF="page205.html#SECTION009100100000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page205.html#SECTION009100100000000000000">Example</A>
<LI> <A NAME="tex2html4441" HREF="page206.html#SECTION009110000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page206.html#SECTION009110000000000000000">Keys and Hash Functions</A>
</UL>
<HR><A NAME="tex2html4436" HREF="page205.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page205.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="tex2html4434" HREF="page203.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page203.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="tex2html4428" HREF="page203.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page203.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="tex2html4438" 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="tex2html4439" 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 © 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 + =
减小字号Ctrl + -
显示快捷键?