3 ms·

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

by natch 8y 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); }

jjnoakes 8y ago
You should look at the actual code, not the abbreviated snippet in the post. The actual code puts values in those variables. And the jre initializes variables to zero, not undefined values (unrelated to the post but a correction to your comment).
ecopoesis 8y ago
This is just shorthand for the blog post: if you read the linked code on GitHub you can see that the three variables are assigned to actual, static random numbers.
gjm11 8y ago
What he means is that to construct a particular instance of this hash function you pick random values a,b,c and do what he describes. You can make multiple different hash functions by picking different random (a,b,c) triples. Now, there are some specific choices of a,b,c that yield bad results. If you pick a=b=0 then your hash function ignores your data. If a or b is a multiple of a large power of 2 then it ignores many bits of your data. If you take e.g. (a,b,c) and (3a,3b,c') then you get two closely-related hash functions. The specific property he's interested in here is that of being "strongly universal" which means that when you pick your hash function at random from whatever family of hash functions you've got, "on average" it behaves well. (Specifically, it means that if you fix two possible inputs and vary your hash function at random then collisions between those two inputs are as rare as they should be.) His family is strongly universal despite the issues I describe above because having enough low-order bits be zero to cause trouble is "rare enough".

by natch 8y ago

jjnoakes 8y ago

You should look at the actual code, not the abbreviated snippet in the post. The actual code puts values in those variables. And the jre initializes variables to zero, not undefined values (unrelated to the post but a correction to your comment).

ecopoesis 8y ago

This is just shorthand for the blog post: if you read the linked code on GitHub you can see that the three variables are assigned to actual, static random numbers.

gjm11 8y ago

What he means is that to construct a particular instance of this hash function you pick random values a,b,c and do what he describes. You can make multiple different hash functions by picking different random (a,b,c) triples. Now, there are some specific choices of a,b,c that yield bad results. If you pick a=b=0 then your hash function ignores your data. If a or b is a multiple of a large power of 2 then it ignores many bits of your data. If you take e.g. (a,b,c) and (3a,3b,c') then you get two closely-related hash functions. The specific property he's interested in here is that of being "strongly universal" which means that when you pick your hash function at random from whatever family of hash functions you've got, "on average" it behaves well. (Specifically, it means that if you fix two possible inputs and vary your hash function at random then collisions between those two inputs are as rare as they should be.) His family is strongly universal despite the issues I describe above because having enough low-order bits be zero to cause trouble is "rare enough".