Computer Chess Club Archives


Search

Terms

Messages

Subject: Hamming distance and lower hash table indexing

Author: Tom Likens

Date: 10:00:05 09/02/03



This is a general query about an issue I've run into and
I'm wondering if anyone else has dealt with it or if I'm
just off base.  Essentially, the issue is this- recently
I started playing around with my hash table's random
numbers to see if I could improve them.  Currently, for
the main table I have a Hamming distance of 24 for
roughly 800 random 64-bit values.

This is where my inquiry comes in, I use the lower N
bits of my hash key as an index into the table.  I'm
wondering, even though the overall Hamming distance is
24 shouldn't I be concerned about the Hamming distance
of the lower N bits?  If these bits are alike, even
though the overal value is reasonable don't it increase
the probablity of hash collisions considerably?
Of course, I won't get a false match since I still use
all 64-bits of the key to indicate if the hash entry
is valid, but it's time wasted performing multiple
probes into the table.

I'm also guessing that this could be more of an issue
for the repetition hash table, since it is quite a bit
smaller than the main table.  Currently, I don't do
multiple probes into this table and I've never seen
an issue.  Still, I'm starting to wonder if there is
a problem lurking below the surface that I may
have missed.

Anyway, I'm probably missing something obvious here.
I intend to run a number of experiments this evening,
but I was curious if anyone else has given this much
thought.

regards,
--tom



This page took 0.07 seconds to execute

Last modified: Thu, 07 Jul 11 08:48:38 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.