Author: Sune Fischer
Date: 12:33:44 03/24/05
Go up one level in this thread
On March 24, 2005 at 13:55:07, Dann Corbit wrote: >On March 24, 2005 at 13:45:20, Alvaro Jose Povoa Cardoso wrote: > >>Hi, >>do you think 10 hash collisions in 2.3 billion nodes is something to worry >>about? > >With a 64 bit hash (and given ideal dispersion) you would see one collision >every 8 billion operations due to the birthday paradox. ~sqrt(2^65) I take it this sqareroot-rule is the solution to the question, "how many persons must be in the room for there to be a 50% chance of a colliding birthday?". With a hash the senario is slightly different. You could say we have a max number of 5 persons in the room at any given time, then people start leaving and others enter the room (that is how the hash works). The question would now be, how many people do we have to exchange in the room before we get a collision with one of the few in the room? >Your rate is 30 times higher than that, but not unreasonably outside of >expectations. Actually the number is very high for a 64 bit key and regular sized hash, usually it would take months to get a collision. If the key is less than 64 bit or the hash is very large, say 10 billion entries, then it would be as expected. -S.
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.