HASHING - Introduction to Java Programming: Comprehensive Version - page 994

As l increases, the probability of a collision increases. Studies show that you should maintain
the load factor under 0.5 for the open addressing scheme and under 0.9 for the separate
chaining scheme.
Keeping the load factor under a certain threshold is important for the performance of hash-
ing. In the implementation of the java.util.HashMap class in the Java API, the threshold
0.75 is used. Whenever the load factor exceeds the threshold, you need to increase the hash-
table size and rehash all the entries in the map into a new larger hash table. Notice that you
need to change the hash functions, since the hash-table size has been changed. To reduce the
likelihood of rehashing, since it is costly, you should at least double the hash-table size. Even
with periodic rehashing, hashing is an efficient implementation for map.

threshold

rehash

Pedagogical Note
For an interactive GUI demo to see how separate chaining works, go to www.cs.armstrong
.edu/liang/animation/HashingUsingSeparateChainingAnimation.html , as shown in Figure 27.8.

separate chaining animation
on Companion Website

F IGURE 27.8

The animation tool shows how separate chaining works.

✓ ✓

27.17

What is load factor? Assume the hash table has the initial size 4 and its load factor is
0.5; show the hash table after inserting entries with the keys 34, 29, 53, 44, 120, 39,
45, and 40, using linear probing.

Check

Point

27.18

Assume the hash table has the initial size 4 and its load factor is 0.5; show the hash
table after inserting entries with the keys 34, 29, 53, 44, 120, 39, 45, and 40, using
quadratic probing.