History hash collisions

Forrest J. Cavalier III mibsoft at mibsoftware.com
Fri Nov 12 15:02:56 UTC 1999


> 
> several months ago, Matt (Dillon) made a similar work with its CRC-16 to
> CRC-64 hash code for Diablo.
> 
> Read http://www.backplane.com/diablo/crc64.html for the details..

I remember seeing that now.  He just did an experiment which
proves the math.

There is another (easier) way to think of the problem.

Suppose you have S possible values, and N of them
are filled without collisions.  What is the probability
that the next randomly calculated value is a collision?

Naturally: N/S.

So with S = 2^48, N = 2.5e6, Probability of collision on
an individual message is 8.882e-9. (that's 1 in 112 million.)
...In other words, on average there is a collision every
112 million messages.

This is Usenet, of course.  But I don't think Oracle or
other commercial-quality databases would stand for
an insertion error (or dropped record) every 112 million
transactions.  That would be a big problem.



More information about the inn-workers mailing list