Hashing Objects

Data Structures and Algorithms with Object-Oriented Design Patterns in C++

Hashing `Object`s

In this section we consider hashing in the context of the object hierarchy defined in Chapter . The abstract base class called Object which was defined in Section has a const virtual member function called Hash which was declared as follows:

class Object
{
    ...
    virtual HashValue Hash () const = 0;
    ...
};

The idea is that every object instance of a class which is derived from the class Object has an associated member function called Hash which hashes that object to produce an integer HashValue. For example, given a reference to an object, Object& obj, the following computation

HashValue x = obj.Hash ();

sets the variable x to the value returned by the Hash function associated with the object to which obj refers.

A Wrapper class template was declared in Section which is used to wrap instances of the C++ built-in data types within an Object abstract interface. Using the Wrapper template, the four classes Char, Int, Double, and String were declared as follows:

typedef Wrapper<char> Char;
typedef Wrapper<int> Int;
typedef Wrapper<double> Double;
typedef Wrapper<string> String;

Since these classes are meant to be concrete classes, they must provide implementations for all of the member functions including the Hash function.

program11556
Program: Wrapper<T> Class Hash Member Function Definition

Program gives the definition of the Hash member function of the Wrapper<T> class. The implementation simply calls the appropriate hashing function from those given in Programs , and . For example the Wrapper<int>::Hash function calls Hash(int) and the Wrapper<string>::Hash function calls Hash(string).