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

Comment onRe^2: The statistics of hashing.