Author: Robert Hyatt
Date: 05:49:21 01/21/99
Go up one level in this thread
On January 20, 1999 at 18:54:37, David Eppstein wrote: >On January 20, 1999 at 16:11:54, Bruce Moreland wrote: >>I still don't understand why this does anything. If you are standing in the >>middle of a crowd and throw a rock in the air, you are going to hit someone in >>the head. I don't see why there is any less chance of hitting someone if you >>throw it so it lands ten feet from you or a hundred. >> >>I don't see why "next to" is a more interesting relationship in a hash table >>than "N away from" is. > >As I understand it, the main reason for double-hashing (i.e. making a hash probe >sequence (h, h+r, h+2r, h+3r...) where both h and r are different hash functions >of the thing you're hashing) is in traditional hashing, where the hash table is >not full, where everything MUST be stored somewhere in the table, and where you >keep probing until you find what you're looking for or hit a blank spot. If you >just probe the sequence (h,h+1,h+2) (or if you use the same r for all values), >you're likely to get big agglomerations of filled entries causing your probe >sequences to be long and slow. > >But, in a chess program, the hash table is full all the time, its ok if some >positions get kicked out of the hash, and you only make a fixed number of >probes, so this argument doesn't seem to apply. > >Does anyone have empirical evidence for or against double hashing? yes... it is bad on a PC because of the way a single cache line fill can suck in multiple consecutive hash entries. It is good on a cray because I get different cpus to probe different combinations of memory banks to reduce bank conflicts and their associated performance cost.
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.