Author: Sune Fischer
Date: 08:10:41 04/07/04
Go up one level in this thread
>>If you have 2^64 different keys and 2^20 of these are already used in the table, >>the probability for the next one (assuming it is different) is going to be 2^46, >>ie. a frequency of 2^-46. 44 of course. :) >>While you are still filling the table the probabilities are lower of course due >>to "fewer kids in the class". >> >>Only new keys not already stored in the table can collide. >>So to get the real frequency one should not count the true hash hits, and there >>will be lots of those too so collision rate is a bit lower. >> >>Another reducing factor is present if you don't probe/store qsearch, since >>collisions on these nodes aren't possible either. >> > >Another issus is how the signatures are created. They are not completely >random, they are related, in that sig(plyx) is based on sig(plyx-1) with some >bits changed. That is a different assumption than in the birthday paradox... Paradox? :) But yes, there are some factors which pull the collision rate up and some which pull it down so it's not easy to estimate the exact theoretical value. The ball park estimates should work okay though, and 1 coll/7 mill nodes sounds like a very high frequency. -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.