Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.java.security > #114

Re: Simple collision ques

Show all headers | View raw

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

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

Back to comp.lang.java.security | Previous | Next — Previous in thread | Find similar

Thread

Simple collision question "puggid" <puggid@THRWHITE.remove-dii-this> - 2011-04-27 16:08 +0000
  Re: Simple collision ques "Tarin Gamberini" <tarin.gamberini@THRWHITE.remove-dii-this> - 2011-04-27 16:08 +0000
  Re: Simple collision ques "Roedy Green" <roedy.green@THRWHITE.remove-dii-this> - 2011-04-27 16:08 +0000

csiph-web