Hashing

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.