Data Structures and Algorithms
with Object-Oriented Design Patterns in C++ 
The Find and FindMatch member functions
of the OpenScatterTable class are defined
in Program 
.
The FindMatch function takes a const reference
to an object and searches the scatter table for
an object which matches the given one.
Program: OpenScatterTable Class FindMatch and Find Member Function Definitions
FindMatch follows the same probing sequence
used by the Insert function.
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 routine makes at most M probes,
where 
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 routine 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 © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.