If we hash a set Sof n keys into a table of size n with a...

 

Transcribed Image Text:

If we hash a set Sof n keys into a table of size n with a universal hash function h, what is the expected maximum number of keys that collide? In other words, what is the maximum number of keys that are expected to hash to the same location? We break down this computation into a sequence of easier steps, as follows. Let A, be the event that at least one slot in the hash table has > j keys. We compute the largest j for which Prob[A] 1/2; that j is our answer. Calculating A, directly is not straightforward, so we proceed as follows. In all cases, explain your reasoning. (a) Let A be the event that the table slot 1 gets > j keys under h. Supposing you know Prob[A], give an upper bound on Prob[A;]. (b) Let B be the event that a fixed subset CCS of size |C| = j hashes into slot 1. That is, each key of C maps to slot 1 under h. Calculate the probability Prob[B]. (c) Use Prob[B] to get an upper bound on the probability Prob[A]]. (d) Compute the largest value of j for which Prob[A] . Explain how in combi- nation with (a), this j is the expected maximum number of collisions. If we hash a set Sof n keys into a table of size n with a universal hash function h, what is the expected maximum number of keys that collide? In other words, what is the maximum number of keys that are expected to hash to the same location? We break down this computation into a sequence of easier steps, as follows. Let A, be the event that at least one slot in the hash table has > j keys. We compute the largest j for which Prob[A] 1/2; that j is our answer. Calculating A, directly is not straightforward, so we proceed as follows. In all cases, explain your reasoning. (a) Let A be the event that the table slot 1 gets > j keys under h. Supposing you know Prob[A], give an upper bound on Prob[A;]. (b) Let B be the event that a fixed subset CCS of size |C| = j hashes into slot 1. That is, each key of C maps to slot 1 under h. Calculate the probability Prob[B]. (c) Use Prob[B] to get an upper bound on the probability Prob[A]]. (d) Compute the largest value of j for which Prob[A] . Explain how in combi- nation with (a), this j is the expected maximum number of collisions.