Author: martin fierz
Date: 02:04:45 11/03/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 ? that's a bit too much, but you're not far off. imagine you have N slots of MAX filled; adding another *random* number gives you a collision probability of N/MAX. so in your case you have to compute the sum over i from 1 to 5000 of i/MAX, which is (sum of i to 5000 of i) divided by MAX, which is i*(i+1)/(2*MAX) = 15.6. did you forget the 2 in the formula for the sum? >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 ? don't worry about it. it'll be very small (order of magnitude N/MAX times smaller than before). for a formula, just use the one above as starting point and generalize it. >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. sorry for being so late... cheers martin
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.