# 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

## 1 Answer

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.)

• But I am not selecting the items randomly, I am selecting the first five. I am not using the decimal number base I am using hexadecimal. Thanks your answer is easy to understand. – kyle k Sep 17 '13 at 20:17
• Ah but you are using SHA1 to compute the hash of the filename. SHA1 is very close to a random function, so we can consider the bottom 5 hexadecimal digits as randomly chosen from the set of all such strings. – pg1989 Sep 17 '13 at 21:34
• @user pg1989 I am not computing the hash of the file name, i am computing the hash of the file contents, I included a link to my code. – kyle k Sep 17 '13 at 23:13
• @kylek, the answer is still correct, regardless of what data you are hashing to get the five digits. – John Deters Sep 17 '13 at 23:43