|
Data Structures and Algorithms
with Object-Oriented Design Patterns in C# |
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 GetHashCode method on the key field.
Program: Association class GetHashCode method.
Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.