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

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

Re: 64-bit hashing function

Show all headers | View raw

On Mon, 21 Apr 2014 09:19:52 +0200, Marcel Müller
<news.5.maazl@spamgourmet.org> wrote, quoted or indirectly quoted
someone who said :

>If you could live with very rare collisions, a 32 bit hash will do as 
>well. String.getHashCode will be fine in this case. It will usually not 
>return the same values for similar strings.

I thought I might collapse a filename to a 64 bit hash, then look it
up in a traditional HashMap.  I just wanted to keep the total size of
the HashMap down.

In essence, the problem is I want to look up by filename (suitably
truncated) to get a Long timestamp, when the file was last
successfully processed without errors. If the current date of the file
matches that, I can bypass processing the file. If current date of the
file, is later than that, I have to reprocess it, and update the
timestamp.

This is basically what I talked the HTML Validator people into
implementing to drastically speed up batch validation. Now I am
preparing to do it to my own HTMLMacros code. (They did not use a
HashMap, but a 0-length matching indicator file with the
last-successfully processed date, and let the OS do the lookup.)

Let us say I write the code presuming collisions are impossible.  What
if one does happen?  Then two files will share the same timestamp. It
will contain the later of the two's timestamp. So if either file needs
reprocessing, the scheme will think both do, hardly a catastrophe
since I process everything all the time now.

There must be a formula to estimate the number of collisions given the
bit-size of the hash and the number of items you hash presuming it is
perfectly random  If not, I suppose I could write a one-shot to find
out experimentally if 64-bits are needed.

I studied probability at UBC, so I am quite capable of deriving the
formula if it is not easily available.
-- 
Roedy Green Canadian Mind Products http://mindprod.com
"Don't worry about people stealing an idea; if it's original, you'll
 have to shove it down their throats." 
~ Howard Aiken (born: 1900-03-08 died: 1973-03-14 at age: 73)

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