(a) (3 points) Suppose we use a hash function h to hash n distinct keys into an array T of length M. Assuming simple uniform hashing, what is the expected number of collisions? (b) For prime p, integer M > 0, and a {0,..., p - 1}, define the function: ha(x) = (ax mod p) mod M Consider the hash function family H = {ha}. (i) (2 point) Find H, the number of unique functions in H. (ii) (10 points) Show that, for any ki + k2, the following holds: Pry(ha(k) = halka)) si Hint: Count the number of a's that that cause collisions in ha and use the number theoretic fact of multiplicative inverses. (iii) (2 points) State whether H is universal. Justify your answer. (c) (3 points) A hash function h: U + {0, ..., M 1} is said to be perfect for a set K CU if h does not cause any collisions among the keys in K. Prove that, for any fixed set K of size at most M, there exists a hash function h that is perfect for K. 2 (a) (3 points) Suppose we use a hash function h to hash n distinct keys into an array T of length M. Assuming simple uniform hashing, what is the expected number of collisions? (b) For prime p, integer M > 0, and a {0,..., p - 1}, define the function: ha(x) = (ax mod p) mod M Consider the hash function family H = {ha}. (i) (2 point) Find H, the number of unique functions in H. (ii) (10 points) Show that, for any ki + k2, the following holds: Pry(ha(k) = halka)) si Hint: Count the number of a's that that cause collisions in ha and use the number theoretic fact of multiplicative inverses. (iii) (2 points) State whether H is universal. Justify your answer. (c) (3 points) A hash function h: U + {0, ..., M 1} is said to be perfect for a set K CU if h does not cause any collisions among the keys in K. Prove that, for any fixed set K of size at most M, there exists a hash function h that is perfect for K. 2