Data Structures and Algorithms
with Object-Oriented Design Patterns in C++ 
Program 
gives the definition of the
default constructor for the ChainedScatterTable::Entry class.
It shall always be the case that an unused entry will have
its object pointer set to zero
and its next field set to null.
By default, all entries are initially unused.
Therefore, the default constructor simply initializes the two
member variables accordingly.
Program: ChainedScatterTable::Entry Class Constructor and ChainedScatterTable Class Constructor, Destructor and Purge Member Function Definitions
The ChainedScatterTable constructor takes a single unsigned int argument which specifies the size of scatter table desired. The constructor simply initializes the HashTable base class and the array member variable as appropriate. Initializing the array variable involves setting all of the entries to the unused state. Consequently, the running time for the ChainedScatterTable constructor is O(M) where M is the size of the scatter table.
The ChainedScatterTable destructor calls the Purge
member function.
The Purge function must delete any contained objects
if the scatter table is the owner of those objects.
The Purge function traverses the array looking for occupied
entries and deletes objects as the are found.
Suppose that there are n contained objects
and the length of the array is M.
Clearly, n cannot be greater than M since all objects
are stored in the array.
The running time of the Purge function is 
and if we assume that 
,
the running time simplifies to O(M).
Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.