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.