What is the probability of a collision when hashing n keys into a hash table…
2018
What is the probability of a collision when hashing n keys into a hash table of size m, assuming that the hash function produces a uniform random distribution?
- A.
O(1/n)
- B.
O(n/m)
- C.
O(logn)
- D.
O(m/n)
Attempted by 308 students.
Show answer & explanation
Correct answer: B
Collision probability increases as the number of keys n grows relative to table size m. This is because more keys create more potential pairs that could map to the same slot, increasing the load factor and collision likelihood.