Author: Pat King
Date: 05:14:16 09/23/98
Go up one level in this thread
On September 22, 1998 at 14:54:11, Dan Newman wrote:
[snip]
>I once measured the hashing error rate for an old program of
>mine (I think it was doing on the order of 100 knps). For
>a 29 bit hash code I was getting between 600 and 900 errors
>per second. At 33 bits I was getting 0-8 errors per second.
>(By errors I mean undetected collisions in which two different
>positions hash to the same code.) So, 32 bits isn't nearly
>enough. I made a guesstimate that 64 bits give me about
>1 error in 1.5 years of runtime--that is perhaps overkill,
>but if we go down just a few bits, then we get a few errors
>per day or hour... (At 41 bits I was getting maybe one
>error per minute.)
>
>The trick I used to measure error rate is to mask off
>some bits of the hash code and use those that are left
>for the index and key. The bits that were masked off were
>used to check for an error. Maybe I could put that more
>clearly... When comparing the key stored in the hash table
>entry with the key for the position, do it twice. Once
>ignoring some bits and once again with all the bits:
>
> if( (entry.key & 0x1fffffff) == (key & 0x1fffffff) ) {
> if( entry.key != key ) nerrors++;
> //etc.
> }
>
>With 3 bits masked off we have a 29-bit hash code (assuming
>we start with 32 bits). This trick fails to detect about 1/8
>of the errors you would get with a 29-bit hash code because we
>have only the 3 masked off bits to do the check. If we
>mask down a 64 bit hashcode to 32 bits we catch virtually all
>the errors this way.
>
>-Dan.
Aha! If everyone does it this way, I understand my confusion. I routinely use
half my key to detect collisions as you do above in your test; it didn't occur
to me that anyone would try "flying blind".
Pat
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.