Author: Uri Blass
Date: 07:48:46 09/25/01
Go up one level in this thread
On September 25, 2001 at 10:24:17, Robert Hyatt wrote: >On September 24, 2001 at 18:06:30, Sune Fischer wrote: > >>On September 24, 2001 at 16:24:01, Robert Hyatt wrote: >> >>>Who cares about the number of hash entries? We aren't scanning the entire table to find a false match. We index to one position only. Suppose the table was 2^64 in size so you could store the entire set of possible hash signatures. >>>Does that increase the chances of a collision? >> >>Yes it does - as Uri has also pointed out. >> >>See, if you make a hash the size of 2^64 and fill it (!) >>then you have no free keys left! >>The next position key you generate will match one >>of those in the table with 100% certainty! >> >>This is the most extreme case, in fact you will never be able >>to update your hash with new positions because you are fooled >>to believe you have calculated them all. You will have a very >>high collision rate in this case. > >I disagree there. "high" is relative. There will be 2^96 different positions >that each map to the same hash table entry. But the search space will not >include _all_ of those unless we somehow find a way to search to the end of >the game. For every entry the search space does not need to include all of the 2^96 positions but only 2 of them to get a collision. If you have 2*2^64 different positions in the search space then you have at least 2^64 collisions in that theoretic case. The reason is that you have 2^64 entries in the hash tables and every hash entry has an average number of 2 positions. Suppose every entry has exactly 2 positions then you get exactly one collision in every entry that means 2^64 collisions other cases can be only worse(for example 4 positions in one entry and 0 positions in another entry mean 3 collisions when 2 positions in every one of them mean 2 collisions) 2^64 collisions when you have 2*2^64 positions means that in half of the cases you got hash collision so the probability is higher because of the size of the hash tables. I am not sure if my explanation is clear and maybe other people can help to explain it more clearly. Uri
This page took 0.01 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.