Author: Heiner Marxen
Date: 09:04:36 12/10/00
Go up one level in this thread
On December 10, 2000 at 04:15:58, Scott Gasch wrote:
>Hi,
>
[snip]
>What are the other schemes people are using? How bad is it to have no
>replacement scheme at all (clobber everything)?
In my experience that is not really bad. What I did not like with the most
trivial replacement strategy, is that it does not make good use of all the
hash table. Until it fills a table with N entries nearly completely,
approximately N replacements have happened.
I improved that with a secondary hash:
primary_hash_index = hashcode % N
secondary_hash_index = (primary_hash_index + hashcode / N) % N
If that entry is also not free, I continue to probe more slots, adding
1, 2, 3, 4 to the last probe index (quadratic rehashing).
When all slots that I have probed are not free, one is going to be replaced.
I choose between the first (primary_hash_index) and the last
(secondary_hash_index + 10)%N: if the draft of the first is smaller or equal
to the draft of the last, the first is replaced, otherwise the last.
According to my experiments this strategy is best for me.
(My program Chest is a mate prover, so take a grain of salt.)
>Thanks,
>Scott
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.