Hashing Containers

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 hashCode 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 hashCode 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 hashCode method and accumulates the result.

  
Program: AbstractContainer class hashCode 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 hashCode 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 © 1998 by Bruno R. Preiss, P.Eng. All rights reserved.