Path: csiph.com!x330-a1.tempe.blueboxinc.net!feeder1.hal-mli.net!news.glorb.com!news-out.readnews.com!news-xxxfer.readnews.com!news-out.news.tds.net!newsreading01.news.tds.net!86597e80!not-for-mail From: "Roedy Green" Subject: Re: Simple collision ques Message-ID: X-Comment-To: comp.lang.java.security Newsgroups: comp.lang.java.security In-Reply-To: References: Content-Type: text/plain; charset=IBM437 Content-Transfer-Encoding: 8bit X-Gateway: time.synchro.net [Synchronet 3.15a-Win32 NewsLink 1.92] Lines: 37 Date: Wed, 27 Apr 2011 16:08:14 GMT NNTP-Posting-Host: 96.60.20.240 X-Complaints-To: news@tds.net X-Trace: newsreading01.news.tds.net 1303920494 96.60.20.240 (Wed, 27 Apr 2011 11:08:14 CDT) NNTP-Posting-Date: Wed, 27 Apr 2011 11:08:14 CDT Organization: TDS.net Xref: x330-a1.tempe.blueboxinc.net comp.lang.java.security:114 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