Author: Heiner Marxen
Date: 09:37:32 01/21/99
Go up one level in this thread
On January 21, 1999 at 08:55:39, Robert Hyatt wrote: >>>>On January 19, 1999 at 14:16:54, Eugene Nalimov wrote: >>>>> D. Knuth, The Art of Computer Programming, Vol.3, >>>>> 2nd edition, pp. 526-531. [snipped lots of interesting discussion] >If you use other bits from the hash signature to 'stride' the probes, you >would get something like this: > > X X X X X X X X > Y Y Y Y Y Y Y Y > >notice how the two buckets have two entries in common and not 6. That is the >main point. Also notice that the two hashes spread things out better, rather >than clumping everything up at the same point in the table (P(hit bucket) is >higher with inc=1 than it is with inc=random). [snip] >get the rehash increment from the hash signature, >(ala' cray blitz). Then there is a good chance that two hash signatures that >match in the lower order N bits (probe index) won't match in the rehash index. Another method (which I happen to use) to avoid bucket overlaps is ``quadratic rehashing´´. Instead of using a constant increment, we linearly increase the steps: inc=1,2,3,4,5,... XX.X..X...X....X .YY.Y..Y...Y....Y ..ZZ.Z..Z...Z....Z Also, the slots of a bucket are still somewhat nearby, which is good for cache locality. Knuth seems to not mention this method, and I do not remember where I found it, so I cannot give a reference. Heiner
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.