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

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

Re: 64-bit hashing function

Show all headers | View raw

On 21.04.14 09.51, Roedy Green wrote:
> 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.

? - The hash map takes the same storage if you hash file names directly.

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

There is no map needed for that purpose at all.

Simply take a single time stamp at program start that is not in the 
future and remember it for the next run. On the next run you need to 
process any files modified not before this time stamp. There is no 
benefit when you know exactly which time stamp of a particular file got 
processed.

If you want to be sure that no file is processed twice then you need to 
process only the modification time stamp interval 
[last_timestamp,current_timestamp).

But be aware of accuracy issues with file time stamps. Depending on the 
file system you might not get what you expected. I.e. if you processed 
up to 2013-04-21T10:20:01.152Z the file system may write the next file 
at 2013-04-21T10:20:00Z (e.g FAT16) or 2013-04-21T10:20:01Z (e.g. 
ext2/3). Although the file is written /after/ your program the time 
stamp is in the past from your point of view, most likely because 
rounding issues. But also without rounding you might not see a change 
immediately during the directory scan. In fact you end up with a race 
condition.
All this preferably applies to remote file systems which might behave 
entirely different than you expect on a particular platform.

A common work around is to introduce a defined latency. I.e. take a time 
stamp let's say 30 seconds in the past at program start. This is used as 
last run the next time.

Like any other make utility this process gets messed up when the time 
stamps of the files are manipulated in an unexpected way. I.e. moving an 
old file into another location or replace it by an old version of the 
same file. Especially on Windows copying a file does not update the last 
write time stamp. You should use the maximum of the last write time 
stamp and the creation time stamp to come around this. Unfortunately the 
latter is not very well accessible with Java before Version 7.


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

I still can't see any reasonable improvement of using hash codes instead 
of file names. If you need to process a file you need the file name anyway.


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

Yes. Look for the Birthday Paradox at Wikipedia.

The birthday is your hash code and only 23 people are required to get a 
50/50 chance of at least one collision. For a 32 bit int you need about 
77,000 objects. All of this assumes an optimal hash function which 
neither the birthday nor String.getHashCode is. So the real values are 
somewhat lower.
But you mentioned that a few collisions do not care you at all.

>  If not, I suppose I could write a one-shot to find
> out experimentally if 64-bits are needed.

There is neither a benefit from 64 bit in your case nor from using hash 
codes instead of file names.


Marcel

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