If h is chosen from a universal collection of hash functions and is used to hash n keys into a table of size m, where n ≤ m, the expected number of…
If h is chosen from a universal collection of hash functions and is used to hash n keys into a table of size m, where n ≤ m, the expected number of collisions involving a particular key K is (b) less than lg n
Show answerHide answer
Correct answer: (A) less than 1
Explanation
This is a theorem in universal hashing: if h is chosen from a universal collection and is used to hash n keys into a table of size m, where n ≤ m, the expected number of collisions involving a particular key is less than 1. So the answer is (a).