Data Structures and Algorithms
with Object-Oriented Design Patterns in C++ 
The Container class
which was defined in Section 
,
abstracts the notion of an object which contains other objects.
The Container class is derived from the Object class
and, therefore, it has a member function called Hash.
What is a suitable hash function for a container?
Given a container c which contains n objects,
, , ..., 
,
we can define the hash function f(c) as follows:
I.e., to hash a container, simply compute the sum of the hash values of the contained objects.
Program shows the implementation
of the Container::Hash function.
This function makes use of the Accept function
to cause a special visitor, HashingVisitor,
to visit all of the objects contained in the container.
When the HashingVisitor visits an object,
it calls that object's Hash function
and accumulates the result.
Program: Container Class Hash Member Function Definition
Since the Accept function is a virtual member function which is defined in the Container class. We assume that all classes derived from the Container class will provide an appropriate implementation for Accept. Note that it is not necessary for any derived class to redefine the behavior of the Hash member function--the behavior inherited from the Container class is completely generic and should suffice for all concrete container classes.
There is a slight problem with Equation .
Different container types that happen to contain identical objects
produce exactly the same hash value.
E.g., an empty stack and an empty list both produce the same hash value.
We have avoided this situation in Program
by adding to the sum the value obtained from hashing the
name of the container itself.
Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.
