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:
must contain every integer between 0 and M-1. This second property ensures that the probe sequence eventually probes every possible array position.