TalkChess.com
Hosted by Your Move Chess & Games

Author Message
Don Dailey

Joined: 29 Apr 2008
Posts: 4323

Post subject: Re: how to measure frequency of hash collisions.    Posted: Sun Jun 17, 2012 1:26 am

Daniel Shawul wrote:
 Don wrote: You can estimate the collision rate by using N bits are for checking. So if your key is 64 bits, pretend it's only 60 bits and 4 bits are for collision testing. If the 4 bits do not match it was a collision. You can extrapolate to get the 64 bit collision rate estimate - each time you add a bit you can expect half the number of collisions. Don

But that won't work because in a hash collision, the hash signature (all 64 bits) are the same for two completely different positions... You need a key from another sequence of random numbers (be it from the same or different hash function). Am I missing something ?

Daniel,

I'm going to do a reset here and answer this post again. I think I understand what caused the misunderstanding. I actually am pretty sure we both misunderstood each other.

My idea is probably a lot simpler than you assumed it to be. Essentially you have 64 hash signatures and 64 random number tables. The signatures are all 1 bit and the random number tables are each 1 bit tables. Due to the magic of 64 bit processors they can all be computed in parallel but that is just a detail.

You can check each of these 64 signatures against each other. If the least significant bit is the same, it might be a match or it may be a collision. You can use the second bit to test that it's a collision with a zero percent false positive but 50% false negative. In other words if the second bit does not match then the first bit is a collision for sure. The more bits you use to test, the more accurate your assessment of whether it's a collision.

You could take 60 of those hash signatures and if they all agree with the 60 signatures of the position being tested against, they probably represent the same position. But you can use 4 more of these independent signatures to see if they agree too. If they don't, you have detected a collision with 100% certainty. By using 4 of these signatures you will detect valid collisions 15 out of 16 times. But once in a while one will slip through undetected. If you want better then you must use more bits.

You did a total context switch which confused me because I was talking about this and you started talking about using separate hash functions. I may have been calling my 64 hash signatures as 64 different hash functions, but the function is really the same XOR function operating on 64 different data so this was probably confusing to you. I was careful this time to call them "signatures"

Does it make sense to you now?
_________________
"Your superior intellect is no match for our puny weapons." -Kang and Kodos
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
Subject Author Date/Time
Daniel Shawul Sat Jun 16, 2012 4:45 pm
Marcel van Kervinck Sat Jun 16, 2012 5:25 pm
Daniel Shawul Sat Jun 16, 2012 6:25 pm
Daniel Shawul Sat Jun 16, 2012 7:15 pm
Don Dailey Sat Jun 16, 2012 9:17 pm
Daniel Shawul Sat Jun 16, 2012 10:05 pm
Don Dailey Sat Jun 16, 2012 10:23 pm
Don Dailey Sat Jun 16, 2012 10:29 pm
Daniel Shawul Sat Jun 16, 2012 11:06 pm
Don Dailey Sat Jun 16, 2012 11:39 pm
Kevin Hearn Sat Jun 16, 2012 11:50 pm
Don Dailey Sun Jun 17, 2012 12:08 am
Daniel Shawul Sun Jun 17, 2012 12:40 am
Daniel Shawul Sat Jun 16, 2012 11:54 pm
Don Dailey Sun Jun 17, 2012 12:23 am
Marcel van Kervinck Sun Jun 17, 2012 7:55 am
Re: how to measure frequency of hash collisions. Don Dailey Sun Jun 17, 2012 1:26 am
Ed Schroder Sat Jun 16, 2012 9:36 pm
Daniel Shawul Sat Jun 16, 2012 10:01 pm
H.G.Muller Sat Jun 16, 2012 10:12 pm
Daniel Shawul Sat Jun 16, 2012 10:31 pm
Daniel Shawul Sun Jun 17, 2012 2:00 am
Rémi Coulom Sun Jun 17, 2012 8:30 am
Daniel Shawul Sun Jun 17, 2012 10:49 am
Daniel Shawul Sun Jun 17, 2012 2:58 pm
Ronald de Man Sun Jun 17, 2012 3:41 pm
Daniel Shawul Sun Jun 17, 2012 5:58 pm
Ronald de Man Sun Jun 17, 2012 9:06 pm
Daniel Shawul Sun Jun 17, 2012 9:57 pm
Lucas Braesch Sun Jun 17, 2012 3:02 am
Ronald de Man Sun Jun 17, 2012 3:08 pm
Daniel Shawul Sun Jun 17, 2012 6:12 pm
Ronald de Man Sun Jun 17, 2012 9:14 pm
Daniel Shawul Sun Jun 17, 2012 10:01 pm
Joshua Shriver Wed Jun 20, 2012 8:45 pm
Ronald de Man Wed Jun 20, 2012 10:44 pm
Joshua Shriver Thu Jun 21, 2012 1:51 am

 Jump to: Select a forum Computer Chess Club Forums----------------Computer Chess Club: General TopicsComputer Chess Club: Tournaments and MatchesComputer Chess Club: Programming and Technical DiscussionsComputer Chess Club: Engine Origins Other Forums----------------Chess Thinkers ForumForum Help and Suggestions
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum