Author: Anthony Cozzie
Date: 16:29:14 11/02/03
Go up one level in this thread
On November 02, 2003 at 18:47:47, Georg v. Zimmermann wrote: >Hi, > >is there some flaw in the following reasoning or does it sound correct: > >Hash table > >A) Conditions > >1) perfect random numbers >2) 800 000 slots >3) 5 000 positions I want to store, all equally important >4) a simple scheme, without any linking between the entries (we dont try another >slot when 1 already full). > >Is it correct that we get about 32 rejected positions ? > >B) >all equal but linking between even and uneven numbered slots (which means we try >exactly 1 slot if another already full). > >How many rejected positions now ? Whats the formular for X linked entries ? > > >Looking forward to a lot of FAST responses, preferably as fast as if I started >another SSDF threat. Cause it is 11:46 pm here and I have too much to work >tomorrow. > >Georg Law of hash tables: collisions are much more likely than you think. In a nutshell, probability of a collision with N insertions into a hash table of size M is: P(N) = 1 - M!/((M^N)*(M-N)!) Which if you think about it makes a lot of sense. My old 15211 book says: If 15 people are in a room, there is a better than 20% chance than 2 of them have the same birthday. Anthony
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.