A hash function maps inputs uniformly onto 1,000,000 buckets. Roughly how many inputs must be hashed before the probability of at least one collision reaches 1/2, and what is the general rule?

A hash function maps inputs uniformly onto 1,000,000 buckets. Roughly how many inputs must be hashed before the probability of at least one collision reaches 1/2, and what is the general rule?

Approach: Approximate the no-collision probability by the exponential of minus the expected number of colliding pairs, then solve for the count that drives that probability to one half.

1178. The expected number of colliding pairs among n inputs is C(n,2)/d, and the collision probability follows the birthday bound: P(no collision) is approximately exp(-n(n-1)/(2d)). Setting that equal to 1/2 gives n = sqrt(2 d ln 2) = sqrt(2 * 10^6 * 0.6931) = 1177.4. So 1178 inputs suffice. The general rule is 1.177 times the square root of d, which reproduces 22.5 at 365 days, the familiar 23 people. The square root scaling is the point: a 64-bit hash collides after about 5 * 10^9 items rather than after 10^19, so the useful security of a hash against collisions is half its bit length.

Follow-up: How many inputs are needed for a 1% collision probability instead of 50%?

Key concepts: birthday bound, expected number of colliding pairs, square root scaling, collision probability.