Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Hashkey collisions (typical numbers)

Author: Sune Fischer

Date: 08:59:58 04/07/04

Go up one level in this thread


>>It is quite similar from the point on where the hash table is full.
>
>absolutely not!
>the probability that *any* two 64-bit signatures are the same goes from 0...1 as
>you increase table size and is about 0.5 at 2^32 entries (and goes to 1 very
>rapidly from there).

I suspect you may in the heat of the moment have thought
that 2^32 is half of 2^64?

It is not of course :)

>the collision probability is given only by the number of independent
>verification bits that you have remaining in your hash signature.
>
>cheers
>  martin

Yes it's not _the_ birthday problem because we are searching for a different
answer, but it is the same setup.

If you have 363 kids in the class and add another kid chance his birthday will
collide is very close to 1.

-S.



This page took 0 seconds to execute

Last modified: Thu, 15 Apr 21 08:11:13 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.