Data Structures and Algorithms
with Object-Oriented Design Patterns in C++ 
Figure: Object Class Hierarchy
A hash table is a searchable container.
As such, its interface provides functions
for putting an object into the container,
finding an object in the container,
and removing an object from the container.
Program 
declares the HashTable class and
Program
gives the definition of the HashTable constructor and
the member function H.
Program: HashTable Class Definition
Program: HashTable Class Constructor and H Member Function Definitions
The HashTable constructor takes a single argument,
and initializes the member variable length accordingly.
The HashTable::H member function
corresponds to the composition 
discussed in Section .
The member function H
takes as its sole argument a const reference to an object.
That object is hashed
and the result of the hash modulo length is returned by H.
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 © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.