Author: Bruce Moreland
Date: 10:06:33 01/19/99
Go up one level in this thread
On January 19, 1999 at 08:13:52, Robert Hyatt wrote:
>On January 18, 1999 at 19:01:01, Dann Corbit wrote:
>(2) use some form of hash 'buckets'. IE in cray blitz,
>I took the low order N bits of the hash signature as the probe address. I took
>the next 10 bits as a 'rehash offset'. (call this RO). I then checked the
>positions at offset, offset+RO, offset+2RO, ... offset+7RO. Either approach is
>ok. The latter tends to solve the 'chaining' problem because two different
>hash keys identical in the last N bits (probe address) still may be different in
>the next 10 bits, giving a different 'bucket'.
I have never understood this logic, and would like to discuss it.
The situation is that you get a collision at one point in the table, and the
question is where to rehash to.
I would like to ask why not just set RO to some constant, for instance one.
You've got a collision in a table that will tend to be full, I don't understand
why the element at some random location in the table is more likely to be empty
or unimportant than the one at the next index in the table.
for (;;) {
if (FOverwrote(index))
return;
index = (index + 1) % tabsize;
}
As opposed to:
ro = (key >> N) & 2047;
for (;;) {
if (FOverwrote(index))
return;
index = (index + ro) % tabsize;
}
I don't see what you get for your extra instructions.
bruce
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.