Simple collision question

Thread view:

puggid@googlemail.com - 29 May 2008 21:00 GMT

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

Reply to this Message

Tarin Gamberini - 30 May 2008 21:44 GMT

puggid@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

Signature

Tarin Gamberini
www.taringamberini.com

Reply to this Message

Roedy Green - 02 Jun 2008 10:47 GMT

>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.

Signature

Roedy Green Canadian Mind Products
The Java Glossary
http://mindprod.com

Reply to this Message

Simple collision question

Free Magazines