Author: Robert Hyatt
Date: 18:56:16 11/15/01
Go up one level in this thread
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... >>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.
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.