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

Re: Java Source of Meiyan Hash Scrambler?

From	Jan Burse <janburse@fastmail.fm>
Newsgroups	comp.lang.java.programmer
Subject	Re: Java Source of Meiyan Hash Scrambler?
Date	2016-06-06 14:13 +0200
Organization	albasani.net
Message-ID	<nj3pcj$5nj$1@news.albasani.net> (permalink)
References	<8d97fe56-983e-412d-bf46-73f46c3e1bae@googlegroups.com> <nj3nuq$5i8$1@dont-email.me>

Show all headers | View raw

Eric Sosman schrieb:
>      Hmmm?  Float.hashCode() uses all thirty-two bits of the float,
> and Double.hashCode() uses all sixty-four bits of the double.  All
> the bits -- including the exponent bits -- contribute to the hashes.

They contribute to the hash code, i.e. the result of hashCode(). But
they don't contribute to the hash table index.

The hash table index is usually calculated:

    int index = key.hashCode() & (table.length - 1);

Oracle/Java has itself recognized that with the lower bit masking to
compute the index, there is a problem for float32 and float64.

So what they do is actually:

    int index = (h = key.hashCode()) ^ (h >>> 16) & (table.length - 1);
    /* See for example source of HashMap implementation,
       static method hash(Object) */

Oracle/Java explicitly mention floats as a reason to do this:

     /**
      * Computes key.hashCode() and spreads (XORs) higher bits of hash
      * to lower.  Because the table uses power-of-two masking, sets of
      * hashes that vary only in bits above the current mask will
vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
      * always collide. (Among known examples are sets of Float keys
      * holding consecutive whole numbers in small tables.)  So we
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
      * apply a transform that spreads the impact of higher bits
      * downward. There is a tradeoff between speed, utility, and
      * quality of bit-spreading. Because many common sets of hashes
      * are already reasonably distributed (so don't benefit from
      * spreading), and because we use trees to handle large sets of
      * collisions in bins, we just XOR some shifted bits in the
      * cheapest possible way to reduce systematic lossage, as well as
      * to incorporate impact of the highest bits that would otherwise
      * never be used in index calculations because of table bounds.
      */

So basically their scramble function is:

    int scramble(int h) {
       return h ^ (h >>> 16);
    }

But this scramble function is still weak for float32 and float64,
for my test table I still get, where the hash table length is 4:

f=1.0, hash(f)=1065369472, scramble(hash(f))%4=0
f=2.0, hash(f)=1073758208, scramble(hash(f))%4=0
f=3.0, hash(f)=1077952576, scramble(hash(f))%4=0
f=4.0, hash(f)=1082146944, scramble(hash(f))%4=0
f=5.0, hash(f)=1084244128, scramble(hash(f))%4=0
f=6.0, hash(f)=1086341312, scramble(hash(f))%4=0
f=7.0, hash(f)=1088438496, scramble(hash(f))%4=0
f=8.0, hash(f)=1090535680, scramble(hash(f))%4=0
d=1.0, hash(d)=1072709616, scramble(hash(d))%4=0
d=2.0, hash(d)=1073758208, scramble(hash(d))%4=0
d=3.0, hash(d)=1074282504, scramble(hash(d))%4=0
d=4.0, hash(d)=1074806800, scramble(hash(d))%4=0
d=5.0, hash(d)=1075068948, scramble(hash(d))%4=0
d=6.0, hash(d)=1075331096, scramble(hash(d))%4=0
d=7.0, hash(d)=1075593244, scramble(hash(d))%4=0
d=8.0, hash(d)=1075855392, scramble(hash(d))%4=0
s=., hash(s)=46, scramble(hash(s))%4=2
s=[], hash(s)=2914, scramble(hash(s))%4=2

So contrary to Oracle/Java claim this scramble function is
not good for float32 and float64 as they describe.

The reason is simple the mantissa for float32 and float64
is at bit 23 respectively 20. So the >>> 16 is for no
avaiable, it still doesn't shift the mantissa to the lowest
bits.

On the other hand, as I showed in my original post,
murmur() is much better.

But how about Meiyan, has anybody some Java code for
Meiyan scrambler. Maybe this is even better than murmur.

Bye

Thread

Java Source of Meiyan Hash Scrambler? bursejan@gmail.com - 2016-06-05 17:22 -0700
  Re: Java Source of Meiyan Hash Scrambler? Eric Sosman <esosman@comcast-dot-net.invalid> - 2016-06-06 07:48 -0400
    Re: Java Source of Meiyan Hash Scrambler? Jan Burse <janburse@fastmail.fm> - 2016-06-06 14:13 +0200
      TreeBins Problem and Float/Double (Was: Java Source of Meiyan Hash Scrambler?) Jan Burse <janburse@fastmail.fm> - 2016-06-06 14:45 +0200
      Re: Java Source of Meiyan Hash Scrambler? Eric Sosman <esosman@comcast-dot-net.invalid> - 2016-06-06 08:47 -0400
      Floating-point hash keys (Was: Java Source of Meiyan Hash Scrambler?) Eric Sosman <esosman@comcast-dot-net.invalid> - 2016-06-06 12:02 -0400
        Re: Floating-point hash keys (Was: Java Source of Meiyan Hash Scrambler?) Roedy Green <inquiry@mindprod.com> - 2016-06-09 05:33 -0700
          Re: Floating-point hash keys (Was: Java Source of Meiyan Hash Scrambler?) Jan Burse <janburse@fastmail.fm> - 2016-06-09 16:27 +0200
  Re: Java Source of Meiyan Hash Scrambler? Roedy Green <inquiry@mindprod.com> - 2016-06-07 03:24 -0700
    Re: Java Source of Meiyan Hash Scrambler? Jan Burse <janburse@fastmail.fm> - 2016-06-07 15:38 +0200
    Re: Java Source of Meiyan Hash Scrambler? Jan Burse <janburse@fastmail.fm> - 2016-06-07 15:39 +0200
      Sideremark II ( Re: Java Source of Meiyan Hash Scrambler?) Jan Burse <janburse@fastmail.fm> - 2016-06-07 15:42 +0200
        Re: Sideremark II ( Re: Java Source of Meiyan Hash Scrambler?) Roedy Green <inquiry@mindprod.com> - 2016-06-09 05:29 -0700
          Re: Sideremark II ( Re: Java Source of Meiyan Hash Scrambler?) Mike Amling <mamling@chaff.us> - 2016-06-09 08:00 -0500
            Re: Sideremark II ( Re: Java Source of Meiyan Hash Scrambler?) Eric Douglas <e.d.programmer@gmail.com> - 2016-06-09 06:07 -0700
              Re: Sideremark II ( Re: Java Source of Meiyan Hash Scrambler?) Jerry Stuckle <jstucklex@attglobal.net> - 2016-06-09 11:41 -0400
              Re: Sideremark II ( Re: Java Source of Meiyan Hash Scrambler?) Roedy Green <inquiry@mindprod.com> - 2016-06-11 01:17 -0700
                Re: Sideremark II ( Re: Java Source of Meiyan Hash Scrambler?) Daniel Pitts <usenet@coloraura.com> - 2016-06-11 12:31 -0700
                Re: Sideremark II ( Re: Java Source of Meiyan Hash Scrambler?) Mike Amling <mamling@chaff.us> - 2016-06-12 15:42 -0500
                Re: Sideremark II ( Re: Java Source of Meiyan Hash Scrambler?) Daniel Pitts <usenet@coloraura.com> - 2016-06-12 21:03 -0700
                Re: Sideremark II ( Re: Java Source of Meiyan Hash Scrambler?) Roedy Green <inquiry@mindprod.com> - 2016-06-13 14:13 -0700
        Re: Sideremark II ( Re: Java Source of Meiyan Hash Scrambler?) Roedy Green <inquiry@mindprod.com> - 2016-06-10 14:11 -0700
      Re: Java Source of Meiyan Hash Scrambler? Roedy Green <inquiry@mindprod.com> - 2016-06-07 20:38 -0700
        Re: Java Source of Meiyan Hash Scrambler? Roedy Green <inquiry@mindprod.com> - 2016-06-09 05:15 -0700
          Re: Java Source of Meiyan Hash Scrambler? Jan Burse <janburse@fastmail.fm> - 2016-06-09 16:26 +0200
            Re: Java Source of Meiyan Hash Scrambler? Roedy Green <inquiry@mindprod.com> - 2016-06-12 02:28 -0700
              Re: Java Source of Meiyan Hash Scrambler? j4n bur53 <janburse@fastmail.fm> - 2016-06-12 12:03 +0200
                Re: Java Source of Meiyan Hash Scrambler? Andreas Leitgeb <avl@logic.at> - 2016-06-13 14:07 +0000
                Re: Java Source of Meiyan Hash Scrambler? Andreas Leitgeb <avl@logic.at> - 2016-06-13 14:17 +0000
                Re: Java Source of Meiyan Hash Scrambler? Andreas Leitgeb <avl@logic.at> - 2016-06-13 14:20 +0000
                Re: Java Source of Meiyan Hash Scrambler? j4n bur53 <janburse@fastmail.fm> - 2016-06-13 16:23 +0200

csiph-web