|
Data Structures and Algorithms
with Object-Oriented Design Patterns in C# |
As explained in Section 
,
a container is an object which contains other objects.
The AbstractContainer class
introduced in Program
implements the Container interface defined in Program .
In this section we show how to define a GetHashCode method
in the AbstractContainer class
that computes a suitable hash function on any container.
Given a container c which contains n objects,
, , ..., 
,
we can define the hash function f(c) as follows:
That is, to hash a container, simply compute the sum of the hash values of the contained objects.
Program gives the code
for the GetHashCode method of the AbstractContainer class.
This method makes use of the Accept method to cause a visitor
to visit all of the objects contained in the container.
When the visitor visits an object,
it calls that object's GetHashCode method
and accumulates the result.
Program: AbstractContainer class GetHashCode method.
Since the Accept method is an abstract method, every concrete class derived from the AbstractContainer class must provide an appropriate implementation. However, it is not necessary for any derived class to redefine the behavior of the GetHashCode method--the behavior inherited from the AbstractContainer 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.
For example, 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
class of the container itself.
Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.
