|
Data Structures and Algorithms
with Object-Oriented Design Patterns in C# |
The Find and FindMatch methods
of the OpenScatterTable class are defined
in Program 
.
The FindMatch method takes a ComparableObject
and searches the scatter table for an object which matches the given one.
Program: OpenScatterTable Class FindMatch and Find methods.
FindMatch follows the same probing sequence used by the Insert method. Therefore, if there is a matching object in the scatter table, FindMatch will make exactly the same number of probes to locate the object as were made to put the object into the table in the first place. The FindMatch method makes at most M probes, where M is the size of the scatter table. However, note that the loop immediately terminates should it encounter an EMPTY location. This is because if the target has not been found by the time an empty cell is encountered, then the target is not in the table. Notice also that the comparison is only attempted for entries which are marked OCCUPIED. Any locations marked DELETED are not examined during the search but they do not terminate the search either.
The running time of the Find method is determined
by that of FindMatch.
In the worst case FindMatch makes n comparisons,
where n is the number of items in the table.
Therefore, the running time of Find is
.
Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.