Author: Uri Blass
Date: 04:32:45 09/23/01
Go up one level in this thread
On September 23, 2001 at 07:11:52, Sune Fischer wrote: >On September 23, 2001 at 02:50:59, Uri Blass wrote: > >>>Why do you think the size of the table has any bearing on the number >>>of collisions? The number of collisions is a function of the >>>"uniqueness" of your key, not how many entries are in your table. >> >>let take an extreme case: >>suppose there is only one entry in your hash tables and you use 64 bit numbers. >> >>The probability for wrong hash collision is 1/2^64 for every new node after the >>first node. > >True > >>If you have 1000000 entries in your hash tables and the hash tables are full >>then the probability for hash collision is 1000000/2^64 for every new node. > >Not so, you don't check you key against all the keys in the hash. I do not understand. I know that basically chess programs compress chess positions to 64 bit numbers The hash tables are basically an array of 64 bit numbers. hash[1048576] Let suppose that the size of the array is 2^20 and you decide which entry to use based on the last 20 bits of the number. if the last 20 bits are 0 then the number is stored in hash[0] if there is nothing in hash[0] if you find a new position that is also a candidate to be stored in hash[0] then it means that you need to check if the position is a new position based on the 64 bit number. The only case when there may be hash collision is case when the position is a new position but you have the same 64 bit number. If the position is a new position then the probability that you have the same 64 bit number is 1/2^44 and not 1/2^64 because you already know the last 20 bits. Uri
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.