Logo Data Structures and Algorithms with Object-Oriented Design Patterns in C++
next up previous contents index

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

displaymath62984

where tex2html_wrap_inline62992 is a hash function, tex2html_wrap_inline62994. To insert item x into the scatter table, we examine array locations tex2html_wrap_inline62998, tex2html_wrap_inline63000, ..., 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

displaymath62985

where tex2html_wrap_inline62822. The function h(x) is the same hash function that we have seen before. I.e., 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

displaymath62986

Property 2
The set of values

displaymath62987

must contain every integer between 0 and M-1. This second property ensures that the probe sequence eventually probes every possible array position.