Using Associations

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. That is, 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 Association class was declared which comprises two fields, a key and a value. Given this declaration, the definition of the hash method for Associations is trivial. As shown in Program , it simply calls the hashCode method on the key field.

  
Program: Association class hashCode method.

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