by Roedy Green <see_website@[EMAIL PROTECTED]
>
Jun 2, 2008 at 09:47 AM
On Thu, 29 May 2008 13:00:58 -0700 (PDT), puggid@[EMAIL PROTECTED]
wrote,
quoted or indirectly quoted someone who said :
>I was wondering if someone tell me how I go about calculating
>collision rates for a "key" that is 2 characters (lowercase alpha
>only) long?
Think about it this way.
To have no collisions with a perfect hash.
for 2 keys and N slots, my odds are 1- (N-1)/N since all slots but 1
are good.
when I add another key, the odds that one will be good too is
1- (N-2)/N.
The odds of all 3 keys going to different slots are:
[1- (N-1)/N] * [1- (N-2)/N]
You should see the pattern.
You can compute this iteratively or factor it to use factorials which
just mask the iteration.
--
Roedy Green Canadian Mind Products
The Java Glossary
http://mindprod.com
