Fast strongly universal 64-bit hashing everywhere

By ingve - 20 hours ago

Showing first level comment(s)

It's "fast" and "strong"? No measurements are given other than one informal speed comparison against murmur64.

What is the goal, and where's the comparison, relative to xxhash, siphash, highwayhash?

https://en.wikipedia.org/wiki/List_of_hash_functions#Non-cry...

I'm not sure what the point of the blog post's universal hash functions is, within the domain of practical software engineering. Who's the audience, programmers or number theorists? Who's going to implement this, and how are they going to choose (or write a function to randomly choose) a, b, and c to give at least adequate properties for their task?

harshreality - 19 hours ago

Uh, wait a second...

64 bit hashing means only 2^64 . Understanding the birthday paradox ( https://en.wikipedia.org/wiki/Birthday_attack ) means that one needs only process 2^32 hashes to find a collision.

Yuck. NO.

crankylinuxuser - 19 hours ago

From the code:

    long a,b,c; // randomly assigned 64-bit values
As I first understood the way this blog post was written, the author was relying on the JRE to populate these uninitialized variables with random values.

Edit: that was an incorrect understanding. It's not shown in the post, but in his real code he actually does assign values to these (thanks for the clarifying replies).

More of the code for context:

    // in Java, long is 64-bit, int 32-bit

    long a,b,c; // randomly assigned 64-bit values

    int hash32(long x) {
      int low = (int)x;
      int high = (int)(x >>> 32);
      return (int)((a * low + b * high + c) >>> 32);
    }

natch - 19 hours ago