Author: Dann Corbit
Date: 14:02:13 11/21/03
Go up one level in this thread
On November 21, 2003 at 16:48:10, K. Burcham wrote: > > >I think you could answer this for me Dann. > >When we set hash at 64 megs and the program ends up needing more than this, is >it your understanding that the program keeps the same assigned addresses on the >ram as the original hash setting and just writes over the top of it? >OR >Do you think that as the program needs more than 64 megs it fills this and >starts assigning new addresses in ram separate from original hash setting and >does not write over the top of the original 64 megs and then will fill as much >ram as the operating system will allow it to? What you are describing is called a hash collision. Let's take a ridiculous example that will hopefully make it clear. Suppose that we allocate a total of 4 hash slots, each consuming 20 bytes of RAM. So our hash table uses 80 bytes. We map chess positions by a final hash of h64bit % 4, to move the hash into slots 0, 1, 2 or 3. Now, as soon as we have a 5th position to store in our hash table it will have to write over top of some other position (assuming that we don't chain to a secondary table or use some other work-around). So I will have to decide on a replacement scheme. One simple scheme is to always replace. No matter how big the hash table is, if the program thinks long enough it will eventually get filled. Now, a hash miss is not important. It just means that we have to recalculate the position instead of using the hash value. The danger with hash tables is a hash collision, where the total hash information (typically the hash slot itself and some key in the position) are identical, but the position is not. However, in practice this is very rare. If you use a 64 bit hash, it is so rare that you can completely ignore it without any worry. Even with 32 bits, it won't affect play much.
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.