If h is chosen from a universal collection of hash functions and is used to…
2014
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 \(\leq\) m, the expected number of collisions involving a particular key K is
- A.
less than 1
- B.
less than
\(lg \ n\) - C.
greater than 1
- D.
greater than
\(lg \ n\)
Attempted by 364 students.
Show answer & explanation
Correct answer: A
Key idea: Use linearity of expectation and the fact that under a universal family each other key collides with a given key with probability 1/m.
There are n - 1 other keys that might collide with the particular key K.
For each other key, the probability of hashing to the same slot as K is 1/m under universal hashing.
By linearity of expectation, the expected number of collisions involving K is (n - 1) * (1/m) = (n - 1)/m.
Since n ≤ m, we have (n - 1)/m < 1.
Conclusion: The expected number of collisions involving the particular key K is less than 1. Therefore the correct answer is "less than 1".