Author: James Swafford
Date: 04:33:02 09/23/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: >>>> >> >> >>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. My friend, I think you're a little confused. Your first calculation is correct if you have a 64 bit key, but it doesn't matter if you have one entry or 1 million entries, so long as you store the full key in the hash table entry and compare that when you pull the record. It is possible for the bits used to probe match, but the full key does not, in which case you still don't have a collision. > >> >>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). > >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.