### Re^2: The statistics of hashing.

by JavaFan (Canon)
 on Apr 01, 2012 at 11:17 UTC ( #962875=note: print w/replies, xml ) Need Help??

in reply to Re: The statistics of hashing.
in thread [OT] The statistics of hashing.

Thus with 110,000 strings, getting a collision in all four stands at 75%**4, about 30% chance. That's with 110,000 strings. You have "several billion".
If, after 110,000 strings you get a 75% on a collision, 75%4 gives you the chance 4 sets of 110,000 each give you a collision. But that's nowhere near the probability the same pair gives you a collision. Which is what BrowserUK needs.

It would take me too much time to dig up the math required to do the calculation. But what BrowserUK may try to do: generate a billion strings that are all unique. Run the proposed algorithm. See how many collisions are reported: they're all false positives. Repeat several times (with different strings). You may even want to calculate a confidence interval. Of course, I've no idea how feasible this is. If it takes a week to process a data set this size, you may not want to do so.

Create A New User
Node Status?
node history
Node Type: note [id://962875]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others studying the Monastery: (4)
As of 2020-12-03 07:16 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
How often do you use taint mode?

Results (51 votes). Check out past polls.

Notices?