Using Associations

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

Using `Association`s

Hashing provides a way to determine the position of a given object directly from that object itself. Given an object x we determine its position by evaluating the appropriate hash function, h(x). We find the location of object x in exactly the same way. But of what use is this ability to find an object if, in order to compute the hash function h(x), we must be able to access the object x in the first place?

In practice, when using hashing we are dealing with keyed data . Mathematically, keyed data consists of ordered pairs

where K is a set of keys, and V is a set of values. The idea is that we will access elements of the set A using the key. I.e., the hash function for elements of the set A is given by

where is the hash function associated with the set K.

For example, suppose we wish to use hashing to implement a database which contains driver's license records. Each record contains information about a driver, such as her name, address, and perhaps a summary of traffic violations. Furthermore, each record has a unique driver's license number. The driver's license number is the key and the other information is the value associated with that key.

In Section the class Association was declared which comprises two objects, a key and a value:

class Association : public Object, public Ownership
{
    Object* key;
    Object* value;
    ...
};

Given this declaration, the definition of the hash function for Associations is trivial. As shown in Program

, it simply calls the Hash member function of the object to which the key member variable points.

program11623
Program: Association Class Hash Member Function Definition