📄 page245.html
字号:
<HTML>
<HEAD>
<TITLE>Removing Items</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="tex2html4945" HREF="page246.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page246.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="tex2html4943" HREF="page241.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page241.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="tex2html4939" HREF="page244.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page244.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="tex2html4947" 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="tex2html4948" 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>
<H3><A NAME="SECTION009644000000000000000">Removing Items</A></H3>
<P>
Removing items from a scatter table using
open addressing has to be done with some care.
The naïve approach would be to locate the item to be removed
and then change the state of its location to <tt>empty</tt>.
However, that approach does not work!
Recall that the <tt>FindMatch</tt> routine which is used to locate an item
stops its search when it encounters an <tt>empty</tt> cell.
Therefore, if we change the state of a cell in the middle of a cluster
to <tt>empty</tt>,
all subsequent searches in that cluster will stop at the empty cell.
As a result, subsequent searches for an object may fail
even when the target is still in the table!
<P>
One way to deal with this is to make use of the third state, <tt>deleted</tt>.
Instead of marking a location <tt>empty</tt>,
we mark it <tt>deleted</tt> when an item is deleted.
Recall that that the <tt>FindMatch</tt> routine was written in such a
way that it continues past deleted cells in its search.
Also, the <tt>FindUnoccupied</tt> routine was written to stop its
search when it encounters either an <tt>empty</tt> or a <tt>deleted</tt> location.
Consequently, the positions marked <tt>deleted</tt> are available
for reuse when insertion is done.
<P>
Program <A HREF="page245.html#proghashtbl11c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page245.html#proghashtbl11c"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> gives the implementation of the <tt>Withdraw</tt>.
The <tt>Withdraw</tt> function takes a reference to an <tt>Object</tt>
and removes it from the scatter table.
It does so by first locating the specific object instance
using <tt>FindInstance</tt> and then marking the location <tt>deleted</tt>.
The implementation of <tt>FindInstance</tt> has been elided.
It is simply a trivial variation of the <tt>FindMatch</tt> routine.
<P>
<P><A NAME="14309"> </A><A NAME="proghashtbl11c"> </A> <IMG WIDTH=575 HEIGHT=219 ALIGN=BOTTOM ALT="program14071" SRC="img1055.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1055.gif" ><BR>
<STRONG>Program:</STRONG> <tt>OpenScatterTable</tt> Class <tt>Withdraw</tt> Member Function Definition<BR>
<P>
<P>
The running time of the <tt>Withdraw</tt> routine is determined
by that of <tt>FindInstance</tt>.
In the worst case <tt>FindInstance</tt> has to examine every array position.
Therefore, the running time of <tt>Withdraw</tt> is
<IMG WIDTH=139 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline62946" SRC="img1005.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1005.gif" >.
<P>
There is a very serious problem with the technique of marking
locations as <tt>deleted</tt>.
After a large number of insertions and deletions have been done,
it will be very likely that there will be no cells left
that are marked <tt>empty</tt>.
This is because, nowhere in any of the routines (except <tt>Purge</tt>)
is a cell ever marked <tt>empty</tt>!
This has the very unfortunate consequence that an unsuccessful search,
i.e., a search for an object which is not in the scatter table,
is <IMG WIDTH=39 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline63214" SRC="img1056.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1056.gif" >.
Recall that <tt>FindMatch</tt> examines at most <I>M</I> array locations
and only stops its search early when an <tt>empty</tt> location is encountered.
Since there are no more empty locations,
the search must examine all <I>M</I> locations.
<P>
If we are using the scatter table in an application in which
we know <em>a priori</em> that no items will be removed,
or perhaps only a very small number of items will be removed,
then the <tt>Withdraw</tt> routine given in Program <A HREF="page244.html#proghashtbl10c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page244.html#proghashtbl10c"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>
will suffice.
However, if the application is such that a significant number of
withdrawals will be made,
a better implementation is required.
<P>
Ideally, when removing an item the scatter table ends up
exactly as it would have appeared
had that item never been inserted in the first place.
Note that exactly the same constraint is met by the <tt>Withdraw</tt>
function for the <tt>ChainedScatterTable</tt> class given
in Program <A HREF="page234.html#proghashtbl7c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page234.html#proghashtbl7c"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>.
It turns out that a variation of that algorithm can be
used to implement the <tt>Withdraw</tt> function
for the <tt>OpenScatterTable</tt> class
as shown in Program <A HREF="page245.html#proghashtbl12c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page245.html#proghashtbl12c"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>.
<P>
<P><A NAME="14311"> </A><A NAME="proghashtbl12c"> </A> <IMG WIDTH=575 HEIGHT=544 ALIGN=BOTTOM ALT="program14099" SRC="img1057.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1057.gif" ><BR>
<STRONG>Program:</STRONG> <tt>OpenScatterTable</tt> Class Alternate <tt>Withdraw</tt> Member Function Definition<BR>
<P>
<P>
The algorithm begins by checking that the scatter table is not empty.
Then it calls <tt>FindInstance</tt> to determine
the position <tt>i</tt> of the item to be removed.
If the item to be removed is not in the scatter table
<tt>FindInstance</tt> returns <tt>length</tt> and an exception is thrown.
Otherwise, <tt>FindInstance</tt> falls between 0 and <IMG WIDTH=75 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline63222" SRC="img1058.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1058.gif" >,
which indicates that the item was found.
<P>
In the general case,
the item to be deleted falls in the middle of a cluster.
Deleting it would create a hole in the middle of the cluster.
What we need to do is to find another item further down in the cluster
which can be moved up to fill in the hole that would be created
when the item at position <tt>i</tt> is deleted.
The purpose of the loop on lines 11-19
is to find the position <tt>j</tt> of an item which can be
moved safely into position <tt>i</tt>.
Note the implementation here implicitly assumes that
a linear probing sequence is used--the <tt>C</tt> function is not called explicitly.
An item at position <tt>j</tt> can be moved safely to position <tt>i</tt>
only if the hash value of the item at position <tt>j</tt>
is not cyclically contained in the interval between <tt>i</tt> and <tt>j</tt>.
<P>
If an item is found at some position <tt>j</tt> that can be moved safely,
then that item is moved to position <tt>i</tt> on line 22.
The effect of moving the item at position <tt>j</tt> to position <tt>i</tt>,
is to move the hole from position <tt>i</tt> to position <tt>j</tt> (line 23).
Therefore, another iteration of the main loop (lines 8-24) is needed
to fill in the relocated hole in the cluster.
<P>
If no item can be found to fill in the hole,
then it is safe to split the cluster in two.
Eventually, either because no item can be found to fill in the hole
or because the hole has moved to the end of the cluster,
there is nothing more to do other than to delete the hole.
Thus, on lines 25-26 the entry at position <tt>i</tt> is set
to <tt>empty</tt> and the associated <tt>object</tt> pointer is set to zero.
Notice that the third state <tt>deleted</tt> is not required
in this implementation of <tt>Withdraw</tt>.
<P>
If we use the <tt>Withdraw</tt> implementation of Program <A HREF="page245.html#proghashtbl12c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page245.html#proghashtbl12c"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>,
the scatter table entries will only ever be in one
of two two states--<tt>occupied</tt> or <tt>empty</tt>.
Consequently, we can improve the bound on the worst-case for the search from
<IMG WIDTH=258 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline63210" SRC="img1054.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1054.gif" > to
<IMG WIDTH=251 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline63226" SRC="img1059.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1059.gif" >,
where <I>n</I> is the number of items in the scatter table.
<P>
Determining the running time of Program <A HREF="page245.html#proghashtbl12c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page245.html#proghashtbl12c"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>
is a little tricky.
Assuming the item to be deleted is actually in the table,
the running time to find the position of that item (lines 3-7) is
<IMG WIDTH=132 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline62846" SRC="img981.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img981.gif" >,
where <IMG WIDTH=72 HEIGHT=9 ALIGN=BOTTOM ALT="tex2html_wrap_inline61308" SRC="img709.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img709.gif" > is the number of item actually in the scatter table.
In the worst case,
the scatter table is comprised of a single cluster of <I>n</I> items,
and we are deleting the first item of the cluster.
In this case,
the main loop on lines 8-24 makes one pass through the entire cluster,
in the worst case moving the hole to the end of the cluster one position
at at time.
Thus, the running time of the main loop is <IMG WIDTH=180 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline63236" SRC="img1060.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1060.gif" >.
The remaining lines require a constant amount of additional time.
Altogether, the running time for the <tt>Withdraw</tt> function is
<IMG WIDTH=141 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline63238" SRC="img1061.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1061.gif" > in the worst case.
<P>
<HR><A NAME="tex2html4945" HREF="page246.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page246.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="tex2html4943" HREF="page241.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page241.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="tex2html4939" HREF="page244.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page244.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="tex2html4947" 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="tex2html4948" 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 + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -