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

Re: 64-bit hashing function

From	wolfgang zeidler <invalid@invalid.invalid>
Newsgroups	comp.lang.java.programmer
Subject	Re: 64-bit hashing function
Date	2014-04-22 20:42 +0200
Organization	(posted via) M-net Telekommunikations GmbH
Message-ID	<lj6d5o$sue$1@news.m-online.net> (permalink)
References	<kfh8l9p1hhphqv5l62am7if9bhnotfse6j@4ax.com> <5354c699$0$6708$9b4e6d93@newsspool2.arcor-online.net> <45i9l9tq8ng6dk1lbfoc97tcj5gbd09iu7@4ax.com> <ein9l99btiltc48sq75lqum8rgblqr4t76@4ax.com>

Show all headers | View raw

Roedy Green wrote:
> On Mon, 21 Apr 2014 00:51:05 -0700, Roedy Green
> [...]
> If the math is right,

I'm sure it is not.

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

Unlikely.
The approximate probability of having one or more collisions within 
20,000 filenames is:
  16 bit : > 1 - 1e300
  32 bit : 0.045
  64 bit : 1.082e-11
128 bit : < 1e300

Have also a look at
http://en.wikipedia.org/wiki/Birthday_attack#Mathematics

-- 
http://wzwz.de/mail

---
Diese E-Mail ist frei von Viren und Malware, denn der avast! Antivirus Schutz ist aktiv.
http://www.avast.com

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