Cover Data Structures and Algorithms with Object-Oriented Design Patterns in Java
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

displaymath61868

where tex2html_wrap_inline61876 is a hash function, tex2html_wrap_inline61878. To insert item x into the scatter table, we examine array locations tex2html_wrap_inline61882, tex2html_wrap_inline61884, ..., 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

displaymath61869

where tex2html_wrap_inline61762. 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

displaymath61870

Property 2
The set of values

displaymath61871

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




next up previous contents index

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