Chi-square test. Use your solution from exercise3.4.30 to check the assumption that the ha...

Chi-square test. Use your solution from exercise3.4.30 to check the assumption that the hash functions for commonly-used key types produce random values.

Exercise 3.4.30:

Chi-square statistic. Add a method to SeparateChainingHashST to compute the ϰ2 statistic for the hash table. With N keys and table size M, this number is defined by the equation

where fi is the number of keys with hash value i. This statistic is one way of checking our assumption that the hash function produces random values. If so, this statistic, for N > cM, should be between M — and M + with probability 1-1/c.