Author: Stuart Cracraft
Date: 11:15:22 01/20/98
Go up one level in this thread
Instead of linear rehashing, how about this. Include an extra field in the transposition table for a linked-list index. This index points to the next transposition table entry in the group of 8 hash slots that constitute the rehash sequence. Then, when a probe or put fails, don't just linear rehash. Instead, in the put case, generate a random number between 0 and the maximum index into the transposition table. Store this in the index field if the put fails at the current index and loop if necessary. In the probe case, just follow the linked list through the various slots that are (randomly) linked together, looking for a probe match. The idea is that a linear rehash algorithm will always block quickly if the same position(s) are hashing to the same address. But in a random rehash algorithm, this is less apt to happen since a random address will be chosen that may not be already occupied, permitting storage instead of collision. Anyone tried this one? --Stuart
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.