Author: Antonio Dieguez
Date: 19:18:31 11/15/01
Go up one level in this thread
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". 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. >>>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.
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.