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

Groups > comp.lang.java.programmer > #28166

Re: 64-bit hashing function

Show all headers | View raw

On Monday, April 21, 2014 5:05:18 AM UTC-4, Roedy Green wrote:
> On Mon, 21 Apr 2014 00:51:05 -0700, Roedy Green
> 
> <see_website@mindprod.com.invalid> wrote, quoted or indirectly quoted
> someone who said :
> 
> >I studied probability at UBC, so I am quite capable of deriving the
> >formula if it is not easily available.
> 
> If the math is right,
> For a 16-bit hashing, 20,000 filenames, you could expect 50,796
> 
> collisions.
> 
> For a 32-bit hashing, 20,000 filenames, you could expect 4 collisions.
> For a 64-bit hashing, 20,000 filenames, you could expect 2 collisions.
> 
> 
I don't think this is correct.  It's pretty clear intuitively that the probability of there being any collisions is something of the order of Nf^2/Nb
where the Nb is the number of bins (e.g., 2^64) and Nf is the number of files.
(Assuming Nf << Nb).

Consider: The first first file has 0 chance of being a collision. There's 1/Nb chance that the second file is a collision, and something very close to 2/Nb that the the third file is a collision and... ~Nf/Nb chance that the Nf file is a collision.  So the sum of these is

Sum (1,Nf)/Nb ~ Nf^2 / (2 Nb).

Here Sum(1,Nf) is defined as the sum of all integers from 1 to Nf.
  
So that would indicate that there the expectation value for collisions in  a 64 bit hash is ~2^(-17) <<< 1.  See http://blog.shay.co/hash-collision-probability/ to do this more rigorously.


Regards,
Tom McGlynn



> 
> This is quite a surprise.  64-bit buys you almost nothing. That
> 
> greatly simplifies my project.
> 
> 
> 
> I will post the program I wrote at
> 
> http://mindprod.com/jgloss/digest.html
> 
> within the hour.
> 
> -- 
> 
> Roedy Green Canadian Mind Products http://mindprod.com
> 

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

Thread

64-bit hashing function Roedy Green <see_website@mindprod.com.invalid> - 2014-04-20 15:15 -0700
  Re: 64-bit hashing function Arne Vajhøj <arne@vajhoej.dk> - 2014-04-20 19:37 -0400
  Re: 64-bit hashing function Roedy Green <see_website@mindprod.com.invalid> - 2014-04-20 22:18 -0700
  Re: 64-bit hashing function Marcel Müller <news.5.maazl@spamgourmet.org> - 2014-04-21 09:19 +0200
    Re: 64-bit hashing function Roedy Green <see_website@mindprod.com.invalid> - 2014-04-21 00:51 -0700
      Re: 64-bit hashing function Roedy Green <see_website@mindprod.com.invalid> - 2014-04-21 02:05 -0700
        Re: 64-bit hashing function taqmcg@gmail.com - 2014-04-21 11:49 -0700
          Re: 64-bit hashing function taqmcg@gmail.com - 2014-04-21 12:01 -0700
        Re: 64-bit hashing function wolfgang zeidler <invalid@invalid.invalid> - 2014-04-22 20:42 +0200
      Re: 64-bit hashing function Marcel Müller <news.5.maazl@spamgourmet.org> - 2014-04-21 12:51 +0200
        Re: 64-bit hashing function Roedy Green <see_website@mindprod.com.invalid> - 2014-04-21 06:31 -0700
          Re: 64-bit hashing function Marcel Müller <news.5.maazl@spamgourmet.org> - 2014-04-21 16:40 +0200
            Re: 64-bit hashing function Roedy Green <see_website@mindprod.com.invalid> - 2014-04-21 20:45 -0700
              Re: 64-bit hashing function Marcel Müller <news.5.maazl@spamgourmet.org> - 2014-04-22 09:46 +0200
        Re: 64-bit hashing function Roedy Green <see_website@mindprod.com.invalid> - 2014-04-21 06:38 -0700
          Re: 64-bit hashing function Roedy Green <see_website@mindprod.com.invalid> - 2014-04-21 06:55 -0700
        Re: 64-bit hashing function Roedy Green <see_website@mindprod.com.invalid> - 2014-04-21 10:09 -0700
          Re: 64-bit hashing function markspace <markspace@nospam.nospam> - 2014-04-21 11:46 -0700
            Re: 64-bit hashing function Roedy Green <see_website@mindprod.com.invalid> - 2014-04-21 20:55 -0700
              Re: 64-bit hashing function markspace <markspace@nospam.nospam> - 2014-04-22 08:39 -0700
            Re: 64-bit hashing function Roedy Green <see_website@mindprod.com.invalid> - 2014-04-21 20:56 -0700
            Re: 64-bit hashing function Roedy Green <see_website@mindprod.com.invalid> - 2014-04-21 21:05 -0700
              Re: 64-bit hashing function markspace <markspace@nospam.nospam> - 2014-04-22 08:15 -0700
            Re: 64-bit hashing function Roedy Green <see_website@mindprod.com.invalid> - 2014-04-25 02:29 -0700
          Re: 64-bit hashing function Roedy Green <see_website@mindprod.com.invalid> - 2014-04-21 20:53 -0700
          Re: 64-bit hashing function Roedy Green <see_website@mindprod.com.invalid> - 2014-05-08 10:12 -0700
            Re: 64-bit hashing function Simon Lewis <simonlewis2001@gmail.com> - 2014-05-08 21:27 +0200
  Re: 64-bit hashing function rossum <rossum48@coldmail.com> - 2014-04-23 09:57 +0100
    Re: 64-bit hashing function Roedy Green <see_website@mindprod.com.invalid> - 2014-04-25 04:08 -0700
      Re: 64-bit hashing function Mike Amling <mamling@chaff.us> - 2014-05-05 11:03 -0500
        Re: 64-bit hashing function Roedy Green <see_website@mindprod.com.invalid> - 2014-05-29 16:00 -0700
        Re: 64-bit hashing function Roedy Green <see_website@mindprod.com.invalid> - 2014-05-29 16:16 -0700

csiph-web