Re: Odds of Recurrence for Hash Function

   From: Chris Babcock <[email protected]>

   Since the hash is a finite size and there are an infinite number of
   possible content bodies, I'm assuming that there is a risk of two
   different messages creating the same hash code. How many messages would
   I have to process to have ~10% chance of a duplicate hash on a 32-bit
   system? Are there any recommendations for salt values so that
   concatenating a pair of hash values would minimize the risk of
   overwriting a message with a non-duplicate? 

Well, it's easy enough to do the calculation.

The 2nd message has 1 chance in 2^32 of colliding.
The 3rd message has 2 chances in 2^32 of colliding
The 4th message has 3 chances in 2^32 of colliding

so you want N such that SUM (1 to N) = 10% of 2^32

2^32 is 4 billion.  10% is 400,000,000 (four hundred million)

Using Euler's shortcut for the sum of all integers, N * (N+1) / 2,
I get a result of about 14,100 messages before a 10% chance of 
collision occurs.

Unfortunately, the current hash does not "feed back" in a way
that would be useful to you (it's a bit linear that way); however
hashing on the first half (or so) of the characters would give
you an independent hash.  So, that would be 2^64 different
filenames, or about 960 million messages before you reach a
10% chance of even one collision.

So do it that way- hash on the entire msg, and hash on only half
of the characters.  (or split the message into two parts, and hash
on both separately).  Either way will give you about a billion 
messages before you get a 10% chance of collision.

	 - Bill Yerazunis


-------------------------------------------------------------------------
This SF.Net email is sponsored by the Moblin Your Move Developer's challenge
Build the coolest Linux based applications with Moblin SDK & win great prizes
Grand prize is a trip for two to an Open Source event anywhere in the world
http://moblin-contest.org/redirect.php?banner_id=100&url=/