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

Scatter Table using Open Addressing

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.