Why would you expect to find a collision in a hash function after approximately $\sqrt{n}$ hashes?

Question

I can't get an intuitive understanding of why it's $2^{(\frac{n}{2})}$ and not $2^n$, where $n$ is the number of bits of which the key consists.

Answer 1

A collision is between two values. If you take a random pair of values you get a 1/2ⁿ chance of having a collision.

With 2^n/2 values you have about 2^n-1 pairs, so you could expect about 1/2 chance of collision.

(That's just the "intuitive way" of thinking about it; in practice, there are mathematical details.)

Answer 2

I think the simple way of looking at it is that it's because the number of pairs between items is roughly proportional to the square of the number of items.

Consider:

2 items-> 1 pair:  AB
3 items-> 3 pairs: AB AC BC
4 items-> 6 pairs: AB AC AD BC BD CD
5 items->10 pairs: AB AC AD AE BC BD BE CD CE DE
6 items->15 pairs: AB AC AD AE AF BC BD BE BF CD CE CF DE DF EF
7 items->21 pairs: AB AC AD AE AF AG BC BD BE BF BG CD CE CF CG DE DF DG EF EG FG
8 items->28 pairs: AB AC AD AE AF AG AH BC BD BE BF BG BH CD CE CF CG CH DE DF DG DH EF EG EH FG FH GH

If you look at these as sequences, the parallel between number of pairs and squares is fairly direct.

For N items, the number of pairs of those items is 1+2+3+...N.

For squares, instead of adding all the numbers, you add only the odd numbers. For example, 4² = 1+3+5+7 (the first four odd numbers).