Author: Robert Hyatt
Date: 20:20:15 11/15/01
Go up one level in this thread
On November 15, 2001 at 22:18:31, Antonio Dieguez wrote: >On November 15, 2001 at 21:56:16, Robert Hyatt wrote: > >>On November 15, 2001 at 08:35:31, Antonio Dieguez wrote: >> >>>On November 14, 2001 at 15:53:18, Koundinya Veluri wrote: >>> >>>... >>>>Hi Bob, >>> >>>Am sorry I am not Bob :) >>> >>>>I have a question. If the hash table index is computed from the hash of the >>>>position then wouldn't collisions happen a lot more often than if the index is >>>>computed independantly of the hash key? >>> >>>Yes. And you are even so right, that the people wich use 64 bits as total hash >>>signature and calculate the hash index with & and store the FULL key in the >>>hashtable, is wasting more ram for nothing!. I'm impressed of this because even >>>Robert Hyatt denied that the other day. >>> >> >>I don't remember denying _anything_. I have _always_ talked about a 64 bit >>hash signature. I store the entire 64 bits for reasons that are not quite >>as obvious as it could be. One is that I move entries from the smaller >>table to the larger table, before overwriting something in the smaller >>table. I need at least one extra hash bit to do this. I also need the >>entire hash signature for some other things I do. And since I use 16 byte >>hash entires, storing 48 bits or 64 bits simply doesn't matter to me at >>all... > >you denied that with the bigger the hashtable, the search becomes less... mmh... >let call it less "super safe". OK.. That I stand by. double the table size, double the probability of a collision. But 2*0 is still zero... >and if you move things from table to table and do other things with the keys >then it is completely understandable if you store the full keys, but you have >named to the fact of storing the full key a kind of "protection" too. No I really didn't. Or if I did I didn't intend to. I use a 64 bit hash signature, _period_. It doesn't matter if I use part of it to store and part of it for the table address, or if I use all of it to store, and part of it for the table address. the result is _identical_ in terms of collisions and everything else. > >>>>If two positions have an identical hash key, then the indeces generated from >>>>this key (say by taking the lowest 8 bits) will also be identical and therefore >>>>the positions hash into the same index in the hash table, causing a collision. >>> >>>Yes, in the case of a full key for everything, if a position comes up with a >>>hashkey that is on the hashtable already then it will collide. So the bigger the >>>hashtable, the bigger the possibility of collisions as there are more keys >>>already there waiting to be repeated. >>> >>>Be well. >> >> >>The probability is so low, however, that it doesn't matter about the size of >>the table. IE the probability of a collision with 64 bits is near zero. >>Doubling the size of the table doubles the probability. But 2 times almost >>zero is _still_ almost zero. > >Ok, I am just very coward. > >Be well. Run a long test. You will become more brave after searching a few trillion nodes with zero problems...
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.