Data Structures and Algorithms with Object-Oriented Design Patterns in C#
next up previous contents index

Hashing Containers

As explained in Section gif, a container is an object which contains other objects. The AbstractContainer class introduced in Program gif implements the Container interface defined in Program gif. 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, tex2html_wrap_inline61929, tex2html_wrap_inline61929, ..., tex2html_wrap_inline61933, we can define the hash function f(c) as follows:

  equation10929

That is, to hash a container, simply compute the sum of the hash values of the contained objects.

Program gif 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.

   program10939
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 gif. 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 gif by adding to the sum the value obtained from hashing the class of the container itself.


next up previous contents index

Bruno Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.