I ran in to this problem and I can't figure it out myself. Can anyone give me a hint?
A linear-hashing scheme with blocks that hold k records uses a threshold constant c, such that the current number of buckets n and the current number of records r are related by r = ckn.
(a) Suppose for convenience that each key occurs exactly its expected number of times. As a function of c, k, and n, how many blocks, including overflow blocks, are needed for the structure?
(b) Keys will not generally distribute equally, but rather the number of records with a given key (or suffix of a key) will be Poisson distributed. That is, if Lambda is the expected number of records with a given key suffix, then the actual number of such records will be i with probability prob_poisson. Under this assumption, calculate the expected number of blocks used, as a function of c, k, and n.
For part (a), there are 2^( ceil( log_2(n) ) - n buckets that represent twice as many keys, thus the number of overflowed record per these buckets is (cnk - nk) / ( 2^( ceil( log_2(n) ) - n ), cnk is the number of total records and nk are those that fit in the first block of each bucket. Divide it by k to obtain the number of buckets, and for the reason that c can be less than 1, I should apply a max function before adding the number of overflow blocks to the total blocks. Then the answer will be n + max( 0, (cn - n) / ( 2^( ceil( log_2(n) ) - n ). Am I correct with this approach? k seems to be missing in my answer
As for part (b), I totally have no idea where to start with. Do I have to first go with the CDF of Poisson distribution to find the probability that this bucket does not overflow, and then sum up the number of over flow buckets multiply by corresponding pmf, in order to find the expected value? Since I am dealing with a Poisson distribution, I need the lambda value for computing pmf, how can I get the lambda?