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

Abstract Hash Tables

As shown in Figure gif, we define an AbstractHashTable class from which several concrete realizations are derived.

   figure10995
Figure: Object class hierarchy.

Program gif introduces the AbstracHashTable class. The AbstractHashTable class extends the AbstractSearchableContainer class introduced in Program gif and it implements the HashTable interface defined in Program gif.

   program11009
Program: AbstractHashTable methods.

Program gif 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 tex2html_wrap_inline61731 discussed in Section gif. 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 gif 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.


next up previous contents index

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