Author: martin fierz
Date: 17:01:19 07/09/02
Go up one level in this thread
On July 09, 2002 at 19:39:27, Scott Gasch wrote: >>i always thought i should do the following experiment one day: reduce the number >>of bits in my "hash lock" (the number i compare to see if the position in the >>hashtable matches the one i'm looking for), and look when the search starts to >>change. that's a one-line change, instead of >>if(hashtable[index].lock == hashlock) you just & both sides with something like >>1<<N-1. you can check the frequency of your hash collision by checking the whole >>lock which should under normal circumstances give close to 0 collisions. > >If I understand you correctly, I'm already doing this. I have 64 bit hash keys >and compute the hash location based on the low N bits of the sig (N depends on >size of hash table). I then verify the sig match based on the high 32 bits. >This is cheaper than verifying the whole 64 bit sig and my debug code asserts >that the full key matches. I've _never_ seen this assert fire though I suppose >it could. > >Scott i'm actually doing something very similar in my program; using two 32bit ints, the first one gets %-ed with the size of the hashtable for the location and i use the second to verify the position. my hashtable size is something like 10^6 entries, = 2^20; so i'm essentially throwing away 12 bits of my hash signature for the comparison. you are doing the same, it seems. i once calculated the probability of a hash collision and since then i have never bothered with it again - it's just way too low. aloha martin
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.