Author: Dann Corbit
Date: 12:07:21 07/29/03
Go up one level in this thread
On July 29, 2003 at 14:32:47, Russell Reagan wrote: >On July 29, 2003 at 13:04:47, Dann Corbit wrote: > >>Collisions are more frequent than people imagine because of the birthday >>paradox. You start running into trouble at around sqrt(key_size) stores, >>typically. > >Are you saying that we can expect to run into collisions with a small repetition >detection table? In the sqrt(key_size), is key_size 64 or 2^64? Think about not only the moves you have played, but also the moves you intend to play (after all, if we already did it, it's a bit late to start thinking about it). Consider a one byte hash, which has 256 distinct values. Now, let's put 16 things in our hash table. A new thing comes along. We form our one byte hash. What are the chances that we have no collision? (1-1/256)^16 = 0.75 With only 16 entries, we have a surprising 1/4 chance of a collision on insert. A far more rigorous [and probably more correct] explanation here: http://burtleburtle.net/bob/hash/birthday.html
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.