Author: Peter McKenzie
Date: 14:07:13 12/09/99
Go up one level in this thread
On December 09, 1999 at 16:17:55, Peter Kappler wrote: >On December 09, 1999 at 15:46:54, Dann Corbit wrote: > >>If I make a hash key of n bits, how can I make a smaller hash table than 2^n. >> >>I don't get it. (e.g. My question about shrinking the hash table was met with >>"It does not matter how small the table is -- it is the size of the key that >>matters."). This caused me to wonder why my brain is so tiny. I mean, how can >>I have a hash table with a great big key and not allocate enough space to hold >>it? Do you have a smaller hash leader (half-key, quarter-key, whatever) and then >>throw the rest into a list of some kind? >> >>What gives? > > >I think your confusion arises from the fact that the hashcode is comprised of >more bits than the hashkey. Most chess programs use a 64-bit hashcode to >represent the current board position, but they only use a subset of this number >(the 20 least-significant bits, for example) to index the table. > >When you write a new entry into the hashtable, one of the fields that you store >in the hash record is the full 64-bit hashcode. This is how collisions are I think this is the thing Dann didn't realise. >resolved - any time you do a lookup, you must verify that the current hashcode >matches the hashcode stored in the table. > >The exception is a "hash-failure" (my lingo, don't know what others call this), >which simply means that your hash function produces the same 64-bit hashcode for >two *different* positions. The odds of this happening are incredibly low (1 / >2^64) for a good hash function. > >I hope this makes sense. Maybe somebody else will post a more concise >explanation. :-) It looked pretty good to me > >--Peter
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.