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

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

displaymath61670

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

displaymath61671

where tex2html_wrap_inline61692 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 gif 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 gif, it simply calls the hashCode method on the key field.

   program10863
Program: Association class hashCode method.


next up previous contents index

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