Author: David Eppstein
Date: 15:54:37 01/20/99
Go up one level in this thread
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?
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.