|
Data Structures and Algorithms
with Object-Oriented Design Patterns in C# |
As shown in Figure 
,
we define an AbstractHashTable class from which
several concrete realizations are derived.
Figure: Object class hierarchy.
Program introduces the AbstracHashTable class.
The AbstractHashTable class extends
the AbstractSearchableContainer class introduced
in Program
and it implements the HashTable interface
defined in Program .
Program: AbstractHashTable methods.
Program introduces the Length property
and three methods, F, G, and H.
The Length property is an abstract property
that provides a get accessor
that returns the length of a hash table.
The methods F, G, and H
correspond to the composition 
discussed in Section .
The F method
takes as an object and calls the GetHashCode method on that
object to compute an integer.
The G method uses the division method of hashing
defined in Section
to map an integer into the interval [0,M-1],
where M is the length of the hash table.
Finally, the H method computes the composition of F and G.
In the following we will consider various ways of implementing hash tables. In all cases, the underlying implementation makes use of an array. The position of an object in the array is determined by hashing the object. The main problem to be resolved is how to deal with collisions--two different objects cannot occupy the same array position at the same time. In the following section, we consider an approach which solves the problem of collisions by keeping objects that collide in a linked list.
Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.