Author: Robert Hyatt
Date: 06:29:06 09/24/01
Go up one level in this thread
On September 23, 2001 at 02:50:59, Uri Blass wrote: >On September 22, 2001 at 23:42:29, James Swafford wrote: > >>On September 22, 2001 at 22:17:06, Uri Blass wrote: >> >>>On September 22, 2001 at 19:08:06, Torstein Hall wrote: >>> >>>>On September 22, 2001 at 18:29:46, Andreas De Troy wrote: >>>> >> >>>If the hash tables are very big then the probability for hash collision can >>>increase and if there are enough hash collisions the result can be a bad move. >>> >>>Uri >> >>Why do you think the size of the table has any bearing on the number >>of collisions? The number of collisions is a function of the >>"uniqueness" of your key, not how many entries are in your table. > >let take an extreme case: >suppose there is only one entry in your hash tables and you use 64 bit numbers. > >The probability for wrong hash collision is 1/2^64 for every new node after the >first node. > >If you have 1000000 entries in your hash tables and the hash tables are full >then the probability for hash collision is 1000000/2^64 for every new node. I will have to think about that, but my first impression is that I don't agree. A single hash position _always_ maps to a single hash table position. If we were storing any entry in any position, I would agree with your logic. But a single entry maps to a single table position, which means that a unique hash signature is going into one position, period, and the number of _other_ positions in the table doesn't affect the probability of a collision at all. If two entries "collide" with the same 64 bit signature, they are also going to collide at the place where they are stored in the table. If they are different in the 64 bits, then they may collide at the place they are stored, but they won't collide in the signature since we just said they are different. I don't believe this reasoning holds, therefore... that the larger the table, the greater the chance of an undetected collision. I believe that the probability of a collision is based solely on the size of the hash signature. > >> >>Maybe my definition of a collision is different than the norm: I >>define a collision as a match of the entire key between different >>positions, not a match of the portion of the key used as a probe into >>the table. > >I also define a collision as a match of the full key(2 different positions with >the same 64 bit number). > In that case this _definitely_ doesn't work. Because a collision is going to be an entry that maps to the same signature _and_ the same table position, independent of the size of the table. >Uri
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.