Data Structures, Algorithms, & Applications in C++
Chapter 10, Exercise 31

(a)

After the last insertion, the 12 chains are [empty, (14), empty, (42), empty, (70), empty, (7), (8, 21, 34), empty, empty, (11), (25, 38)].

(b)

The loading factor is 10/13 = 0.77.

(c)

The number of buckets examined during an unsuccessful search that starts at home bucket i is [0, 1, 0, 1, 0, 1, 0, 1, 3, 0, 0, 1, 2]. The average is 10/13 = 0.77.

(d)

When searching for each of [7, 42, 25, 70, 14, 38, 8, 21, 34, 11] the number of buckets examined is [1, 1, 1, 1, 1, 2, 1, 2, 3, 1]. The average is 14/10 = 1.4.

(e)

When the loading density is 0.77, the formulas yield 0.77 and 1.39 as the expected value for the average number of buckets examined in an unsuccessful and a successful search, respectively. These numbers are almost identical to those in our example. Despite this, you should remember that the formulas do not tell you what will happen in an individual case but what happens on average as the number of elements in the table becomes very large.