|
Data Structures and Algorithms
with Object-Oriented Design Patterns in Ruby |
A hash table is a searchable container. As such, it provides methods for putting an object into the container, finding an object in the container, and removing an object from the container.
Program 
introduces the HashTable class.
The abstract HashTable class extends
the the abstract SearchableContainer class
defined in Program .
Program: Abstract HashTable class.
Program declares the length method
to be an abstract method.
Concrete classes derived from HashTable must override this method.
Program also defines the method called loadFactor.
The purpose of this method is explained in Section .
Program continues the definition
of the HashTable class.
Three methods, f, g and h, are defined.
Program: Abstract HashTable class f, g and h methods.
The methods f, g, and h
correspond to the composition 
discussed in Section .
The f method
takes as an object and calls the built-in hash function 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.
Figure shows the class hierarchy
for the classes discussed in this chapter.
These classes illustrate various ways of implementing hash tables.
In all cases,
the underlying implementation of the hash table 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 next section,
we consider an approach which solves the problem of collisions
by keeping objects that collide in a linked list.
Figure: Object class hierarchy.
Copyright © 2004 by Bruno R. Preiss, P.Eng. All rights reserved.