Hashing as a Dictionary Implementation - Data Structures and Abstractions with Java - page 548

FIGURE 22-3

The average number of comparisons required by a search of the
hash table for given values of the load factor λ when using

separate chaining

λ

Unsuccessful Search Successful Search

0.1
0.3
0.5
0.7
0.9
1.1
1.3
1.5
1.7
1.9
2.0

0.1
0.3
0.5
0.7
0.9
1.1
1.3
1.5
1.7
1.9
2.0

1.1
1.2
1.3
1.4
1.5
1.6
1.7
1.8
1.9
2.0
2.0

Note: Maintaining the performance of hashing
Collisions and their resolution typically cause the load factor to increase and the efficiency

of the dictionary operations to decrease. To maintain efficiency, you should restrict the size of
λ

λ

as follows:

λ < 0.5 for open addressing

λ < 1.0 for separate chaining

Should the load factor exceed these bounds, you must increase the size of the hash table, as
the next section describes.

Rehashing

22.7

The previous section discussed the efficiency of hashing as a dictionary implementation when
using various ways of resolving collisions. As you saw, to ensure an efficient implementation, you
must not let the load factor and see whether it exceeds

the upper limit for the particular collision resolution scheme, as given in the previous note.
So what do you do when

λ get too large. You can readily compute λ

reaches its limit? First, you can resize the array that serves as the
hash table, as described in Chapter 2. Typically, you double the size of an ordinary array, but here
you need to ensure that the array's size is a prime number. Expanding the array's size to a prime
number that is at least twice its previous size is not too difficult.
Ordinarily, when you expand an array, the next step is to copy the contents of the original array
into corresponding locations of the new array. This is not the case for a hash table, however. Since
you have changed the size n of the hash table, the compression function c % n will compute different
indices than it did for the original hash table. For example, if the hash table originally contained
101 locations, the function c % 101 compresses the hash code 505 to the index 0. The new hash
table will contain 211 locations, since 211 is the smallest prime number greater than 2 times 101.
But now c % 211 compresses 505 to the index 83. You cannot simply copy the location at index 0

λ