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