Two key sets colliding in one hash table

Question

Set A has 50 keys and set B has 50 keys, all hashed into the same table of 1000 slots (each key lands in a uniformly random slot independently). What is the probability that at least one key from A lands in the same slot as at least one key from B?

Accepted Answer

This is a cross collision: we want an A key and a B key sharing a slot, ignoring clashes within a single set. Count the cross pairs: 50 	imes 50 = 2500 	ext{ cross pairs}. Each cross pair collides with probability 1/1000. The chance of no cross collision is approximately P(	ext{no cross collision}) \approx e^{-2500/1000} = e^{-2.5} \approx 0.082. Therefore P(	ext{at least one cross collision}) \approx 1 - 0.082 \approx 0.918, about 92\%. The expected number of cross-colliding pairs is 2500/1000 = 2.5, well above 1, so a cross clash is nearly certain. Takeaway. Cross collisions scale with …

Two key sets colliding in one hash table

Your answer

Discussion

Learn the concepts

Related questions