Generate unique ID for URL

Dave Angel d at
Wed Nov 14 13:33:47 CET 2012

On 11/14/2012 06:29 AM, Johannes Bauer wrote:
> <snip>
> When doing these calculations, it's important to keep the birthday
> paradox in mind (this is kind of counter-intuitive): The chance of a
> collission raises tremendously when we're looking for *any* arbitrary
> two hashes colliding within a certain namespace. The probability you've
> calculated is the pre-image probability (which you also again need to
> multiply with a factor of two, because when trying to collide one given
> hash, in the mean case you'll only have to search *half* the namespace
> before finding a collision).
> <snip>

Te birthday paradox could have been important had the OP stated his goal
differently.  What he said was:

"""Ideally I would want to avoid collisions altogether. But if that means significant extra CPU time then 1 collision in 10 million hashes would be tolerable."""

That means that he's willing to do the necessary overhead of collision
resolution, once in every 10 million lookups.  That's not the same as
saying that he wants only one chance in 10 million of having ANY
collisions among his data items.



More information about the Python-list mailing list