Data Structures and Algorithms
with Object-Oriented Design Patterns in C++ 
This section describes an implementation of a scatter table
using open addressing with linear probing.
Program 
declares the OpenScatterTable class.
The scatter table is implemented as an array
of elements of the nested type Entry.
Each Entry instance has two member variables--object and state.
The former is a pointer to an Object class instance.
The latter is an element of the enumeration State.
Program: OpenScatterTable Class Definition
Each entry can be in one of three states--empty, occupied, or deleted. Initially, all entries are empty. When an object pointer is recorded in an entry, the state of that entry is changed to occupied. The purpose of the third state, deleted, will be discussed in conjunction with the Withdraw function below.
In addition to the lone member variable array, the OpenScatterTable class definition contains a number of private member function declarations--C, FindUnoccupied, FindMatch, and FindInstance. The member function C embodies the collision resolution strategy which is this case is linear probing. The other three member functions encapsulate functionality which is useful in implementation of the various scatter table operations.
Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.