Hash tables - Data Structures and Problem Solving Using Java - page 779

linear probing

20.3

Now that we have a hash function, we need to decide what to do when a colli-
sion occurs. Specifically, if X hashes out to a position that is already occupied,
where do we place it? The simplest possible strategy is linear probing, or
searching sequentially in the array until we find an empty cell. The search
wraps around from the last position to the first, if necessary. Figure 20.5
shows the result of inserting the keys 89, 18, 49, 58, and 9 in a hash table
when linear probing is used. We assume a hash function that returns the key X
mod the size of the table. Figure 20.5 includes the result of the hash function.
The first collision occurs when 49 is inserted; the 49 is put in the next
available spot—namely, spot 0, which is open. Then 58 collides with 18, 89,
and 49 before an empty spot is found three slots away in position 1. The col-
lision for element 9 is resolved similarly. So long as the table is large
enough, a free cell can always be found. However, the time needed to find a
free cell can get to be quite long. For example, if there is only one free cell
left in the table, we may have to search the entire table to find it. On average
we would expect to have to search half the table to find it, which is far from
the constant time per access that we are hoping for. But, if the table is kept
relatively empty, insertions should not be so costly. We discuss this
approach shortly.

In linear probing,
collisions are
resolved by
sequentially scan-
ning an array (with
wraparound) until
an empty cell is
found.

figure 20.5
Linear probing hash
table after each
insertion

hash ( 89, 10 ) = 9
hash ( 18, 10 ) = 8
hash ( 49, 10 ) = 9
hash ( 58, 10 ) = 8
hash ( 9, 10 ) = 9

After insert 89 After insert 18 After insert 49 After insert 58 After insert 9

0 49 49 49

1 58 58

2 9

3

4

5

6

7

8 18 18 18 18

9 89 89 89 89 89