Into a 10-long hash table, with hash function h(x) = x mod 10, insert
the following sequence of keys:
11, 33, 83, 99, 34, 19, 49.
Show results for four cases. 1) separate chaining, 2) linear hashing, 3) quadratic hashing, 4) double hashing with 2nd hash function 7-(x mod 7).
sep ch lin quad doub 0 19 19 1 >11 11 11 11 2 49 3>83>33 33 33 33 4>34 83 83 83 5 34 34 34 6 49 7 19 8 49 9>49>19>99 99 99 99
5) λ, the load factor, is .7 for all cases.
6) λ, here .7, is always the average length of a sep. chaining
list.
7) All of them. One cluster: 9,0,...4,5.
8) This question, like so many, was a little deeper than I first
thought. 5 - (x mod 5) sets off alarm bells, since 5 divides the
table length 10. But that's not really the issue. Both second hash
functions, both 7 - (x mod 7) or 5 - (x mod 5) can generate both 2
and 5 as the stepping amount. In case of 2, only 5 table
positions are available for either fn, and in case of 5, only two
locations for either. So for "mod 7" function these bad cases happen 2/7 of the time or
about 28%, and for the other they happen 2/5 of the time, or 40%. So
the "mod 7" function is indeed better, but only because it's larger.