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

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

TreeBins Problem and Float/Double (Was: Java Source of Meiyan Hash Scrambler?)

Show all headers | View raw

Jan Burse schrieb:
>
> 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.

I wouldn't be surprised, that in practical scenarios,
with better scrambling the switching from list bins to tree
bins would less often happen.

tree bins have recently been introduced in the implementation
of HashMap, making them a little bit more heavy weight.
Oracle/Java writes here:

     /**
      * Because TreeNodes are about twice the size of regular nodes, we
      * use them only when bins contain enough nodes to warrant use
      * (see TREEIFY_THRESHOLD). And when they become too small (due to
      * removal or resizing) they are converted back to plain bins.  In
      * usages with well-distributed user hashCodes, tree bins are
      * rarely used.  Ideally, under random hashCodes, the frequency of
      * nodes in bins follows a Poisson distribution
      * (http://en.wikipedia.org/wiki/Poisson_distribution) with a
      * parameter of about 0.5 on average for the default resizing
      * threshold of 0.75, although with a large variance because of
      * resizing granularity. Ignoring variance, the expected
      * occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
      * factorial(k)). The first values are:
      */

But the distribution assumption is probably broken for
float32 and float64, since they have a particular bit pattern,
see the IEEE 754 spec.

float32 example:
https://de.wikipedia.org/wiki/IEEE_754#/media/File:IEEE-754-single.svg

The mantissa is always shifted away from the lowest bits, and
the exponent counts this shift. The binary point between mantissa
integral part and fractional part without the exponent is directly
represented in the bits after the exponent.

The mantissa is assumed to be 1 =< m < 2.

Back to comp.lang.java.programmer | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

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