|
Data Structures and Algorithms
with Object-Oriented Design Patterns in Python |
As explained in Section 
,
a container is an object which contains other objects.
In this section we show how to define a __hash__ method
for the abstract Container class defined
in Program -Program .
The method given 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 __hash__ method of the abstract Container class.
This method implicilty uses an iterator
to enumerate all of the objects contained in the container.
It calls the built-in hash function on each object in the container
and accumulates the result.
Recall that the hash function
calls an object's __hash__ method.
Program: Container class __hash__ method.
Every concrete class derived from the Container class provides an appropriate iterator implementation. However, it is not necessary for any derived class to redefine the behavior of the __hash__ method--the behavior inherited from the abstract 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.
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 © 2003, 2004 by Bruno R. Preiss, P.Eng. All rights reserved.
