Author: Peter Fendrich
Date: 13:44:16 12/09/99
Go up one level in this thread
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???
Supposing that you have computed the Hashindex as told above and have a new data
to store and find out that the old entry is occupied and doesn't have the same
hashkey (or part of hashkey - this is an implementaion issue) as the new entry.
That's a collision! Now there are a few different strategies.
For example:
1) Replace the old entry with the new one, always.
2) Replace the old entry with the new one
if the search depth of the new one is >= the depth of the old one.
3) Design two hash tables and if you have a collision, place the most
accurate entry (by search depth) in the first table and the other one in
the second table.
The second table is always replaced when collision occurs.
I think that 3) is the best one.
If both the new an old entry has the same hashkey it's not a collision, as far a
we know without further testing. Then it's only a case of updating the entry.
With further testing it's possible to find out if we have a collision even if
the hashkeys are identical:
- Store some age variable in the entry. A few bits that are set in the root of
the search. 4 bits can handle 16 generations before starting all over again.
- Check if the move in the old entry is possible to make. if not, we have a
collision.
- and more
//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.