If h is chosen from a universal collection of hash functions and is used to…
2017
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 x is less than _______.
- A.
1
- B.
1/n
- C.
1/m
- D.
n/m
Attempted by 383 students.
Show answer & explanation
Correct answer: A
Key insight: under a universal family of hash functions, any two distinct keys collide with probability 1/m.
Derivation:
For a fixed key x and any other key y, Pr[h(y) = h(x)] = 1/m.
There are n-1 other keys, so the expected number of collisions involving x is the sum of these probabilities: (n-1) * (1/m) = (n-1)/m.
Since n ≤ m, we have (n-1)/m ≤ (m-1)/m < 1, so the expected number of collisions involving x is strictly less than 1.
Conclusion: The expected number of collisions involving a particular key is less than 1.