Probability of collision when using a 32-bit hash

Question

I have a 10-character string key field in a database. I've used CRC32 to hash this field, but I'm worrying about duplicates. Could somebody show me the probability of collision in this situation?

P.S.: My string field is unique in the database. If the number of string fields is 1 million, what is the probability of a collision?

score 117 · Accepted Answer · edited May 23 '17 at 10:29

117

Duplicate of Expected collisions for perfect 32bit crc

The answer referenced this article: http://arstechnica.com/civis/viewtopic.php?f=20&t=149670

Found the image below from: http://preshing.com/20110504/hash-collision-probabilities

enter image description here

edited May 23 '17 at 10:29

Community

1
1

answered Jan 08 '13 at 07:45

Adam Morris

8,265
12
45
68

3

SO WHAT's THE ANSWER? – Tommix Jan 18 '23 at 14:16

Mark Adler · Answer 2 · 2013-01-08T21:17:57.983

47

In the case you cite, at least one collision is essentially guaranteed. The probability of at least one collision is about 1 - 3x10^-51. The average number of collisions you would expect is about 116.

In general, the average number of collisions in k samples, each a random choice among n possible values is:

N(n,k)~=k(k-1)/(2n)

The probability of at least one collision is:

p(n,k)~=1-e^(-k(k-1)/(2n))

In your case, n = 2³² and k = 10⁶.

The probability of a three-way collision in your case is about 0.01. See the Birthday Problem.

edited Jan 08 '13 at 21:17

answered Jan 08 '13 at 14:45

Mark Adler

101,978
13
118
158

Thank you so much, I wonder that this probability still depend on CRC32 algorithm ? – nguyenngoc101 Jan 11 '13 at 10:03
2

Any good 32-bit hash algorithm will give exactly the same result. – Mark Adler Jan 11 '13 at 16:50

Probability of collision when using a 32-bit hash

2 Answers2

Linked