Author: Daniel Clausen
Date: 13:21:22 12/09/99
Go up one level in this thread
Hi
On December 09, 1999 at 16:03:02, Dann Corbit wrote:
>On December 09, 1999 at 15:58:51, Daniel Clausen wrote:
>>Hi
>>
>>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?
>>
>>If you have a hash key of e.g 64 bits and a good algorithm to create it, all
>>bits are of
>>'equal quality'. So you can for example use the 1st 20 bits for the index in a
>>hash
>>table of 2^20 entries. The index in the hashtable is "key & (hashEntries-1)".
>>
>>One hash entry should hold the complete hashkey. If you get a hash-hit, you
>>should
>>compare the complete hash-key in the hash table with the hash-key of the current
>>position. If they're not equal, you got a collision.
>How are collisions handled? Do you compute the value for the current key and
>replace or???
Depends:
Storing a value into the HT:
If the depth of the position in the HT is less then the current depth, I
overwrite.
Accessing a value from the HT:
If I get a collision, it's simply not a hit and it's like you didn't find
anything.
Here's some pseudo-code:
BOOL probeHT(Position p, ...)
{
int index = p.hashValue & (HASH_ENTRIES-1);
HashEntry entry = hashTable[index];
// Return immediately if there's no entry.
if(entry.isOccupied == FALSE) return FALSE;
// Now we have to check if the complete (64bit) hashkey
// of the current position is the same as the stored one
// in the hashtable. If not, we also return.
if(entry.hashValue != p.hashValue) return FALSE;
}
void storeHT(Position p, int currentDepth, ...)
{
int index = p.hashValue & (HASH_ENTRIES-1);
// Store info if the slot is still free.
if(hashTable[index].isOccupied == FALSE)
{
// ... store stuff
return;
}
// If the slot is already occupied by another position, which
// 'accidently' has the same index as the current position,
// overwrite the slot, if the depth of this position is higher
// than the depth of the current entry.
// By depth I mean the #plies the position was analysed.
if(hashTable[index].depth < currentDepth)
{
// ... store stuff
}
}
I hope people correct me if I missed something here.
Kind regards,
-sargon
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.