Author: Robert Hyatt
Date: 19:59:53 11/02/03
Go up one level in this thread
On November 02, 2003 at 19:29:14, Anthony Cozzie wrote: >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 Even better, with 30 people in the room, the probability approaches 1.0 that two have the same birthday. By _far_ the more important question is, "how much will a collision hurt the search?" Not "how many will I get?"
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.