Data Structures and Algorithms
with Object-Oriented Design Patterns in C++ 
The constructor and destructor for the ChainedHashTable
class are defined in Program 
.
The constructor takes a single argument of type unsigned int
which specifies the size of hash table desired.
The constructor simply initializes the HashTable base class
and the array member variable accordingly.
Initializing the array variable involves constructing
the required number of empty linked lists.
Consequently, the running time for the ChainedHashTable
constructor is O(M) where M is the size of the hash table.
Program: ChainedHashTable Class Constructor, Destructor and Purge Member Function Definitions
The ChainedHashTable destructor simply calls the Purge member function. Since the ChainedHashTable is a container, the Purge function must delete any contained objects if it is the owner of those objects. Therefore, the Purge function is required to traverse each of the linked lists in the array.
To determine the running time of the Purge function,
we will assume that there are n contained objects
and the length of the array is M.
Furthermore, let 
be the number of items
in the 
linked list
for 
.
Note that 
.
The running time of the inner loop
for the iteration of the outer loop
is 
.
The constant overhead arises from the loop termination test
which must be done at least once.
The total running time of the destructor is given by
If we assume that 
,
the running time simplifies to O(M+n).
Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.