# probability of N hash digits colliding

What is the probability of the first N hash digits colliding? for example i made a script that appends the first 5 digits of the file's sha1 hash to the name of the file.

So will the probability of a collision be 16^5=1048576? Am i properly calculating the probability of a collision.

-
In discrete probability any event occurs with probability at most 1. You can expect a collision of the first 5 digits of a SHA1 hash after roughly 1000 hashes because of the birthday bound. –  pg1989 Sep 17 '13 at 18:35

The birthday problem is the generic name for such questions. You have $n$ values, selected randomly and uniformly in a space of size $t$; the probability that at least two of these values are identical is roughly equal to $n^2/(2t)$. When $n$ becomes close to $\sqrt{t}$, then the probability raises sharply. In your case, with 5 hexadecimal digits, you have a space of size $t = 16^5$, so you can expect your first collision, on average, when you get about 1000 values or so.
An intuitive way to think about it is that $n$ values make about $n^2/2$ pairs, and, "somehow", each pair has probability $1/t$ of being a collision. (The pairs are not independent of each other, but the intuition still works in that case.)