Author: Peter Kappler
Date: 13:17:55 12/09/99
Go up one level in this thread
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 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. :-) --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.