Data Structures and Algorithms
with Object-Oriented Design Patterns in C# |

An alternative method of dealing with collisions
which entirely does away with the need for links and chaining
is called *open addressing* .
The basic idea is to define a *probe sequence*
for every key which, when followed, always leads to the key in question.

The probe sequence is essentially a sequence of functions

where is a hash function, .
To insert item *x* into the scatter table,
we examine array locations , , ...,
until we find an empty cell.
Similarly, to find item *x* in the scatter table
we examine the same sequence of locations in the same order.

The most common probe sequences are of the form

where .
The function *h*(*x*) is the same hash function that we have seen before.
That is, the function *h* maps keys
into integers in the range from zero to *M*-1.

The function *c*(*i*) represents the collision resolution strategy.
It is required to have the following two properties:

**Property 1**-
*c*(0)=0. This ensures that the first probe in the sequence is **Property 2**- The set of values
must contain every integer between 0 and

*M*-1. This second property ensures that the probe sequence eventually probes*every possible array position*.

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