Simple collision question

[puggid]

To: comp.lang.java.security
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?

I realise it's 26x26 but if I generate two random numbers between 1-26
is that all that's involved? So each time I generate this key, I have
a 1/676 chance of a collision?

Thanks for the help

---
* Synchronet * The Whitehouse BBS --- whitehouse.hulds.com --- check it out free usenet!
--- Synchronet 3.15a-Win32 NewsLink 1.92
Time Warp of the Future BBS - telnet://time.synchro.net:24

[Tarin Gamberini]

To: comp.lang.java.security
pug...@googlemail.com ha scritto:
[cut]

> I realise it's 26x26 but if I generate two random numbers between 1-26
> is that all that's involved? So each time I generate this key, I have
> a 1/676 chance of a collision?
>

I think that what you said is right if your random source gives numbers
uniformly distributed. Check out this
http://en.wikipedia.org/wiki/Uniform_distribution_%28discrete%29

So, how your random source generates numbers? Check out this
http://en.wikipedia.org/wiki/Random_number_generator too.

Bye,
Tarin

--
Tarin Gamberini
www.taringamberini.com

[Roedy Green]

To: comp.lang.java.security
On Thu, 29 May 2008 13:00:58 -0700 (PDT), pug...@googlemail.com 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