Bounds Check Elimination with Fast-Range

[August Nagro]

Yes, exactly. Once can also use Fibonacci hashing to ensure that an
arbitrary Key.hashCode() is well distributed.

See for instance my implementation of Universal Hashing..
https://gist.github.com/AugustNagro/4f2d70d261347e515efe0f87de9e8dc2

On Mon, Nov 18, 2019 at 11:45 AM John Rose <john.r.rose at oracle.com> wrote:

> On Nov 18, 2019, at 5:10 AM, Florian Weimer <fweimer at redhat.com> wrote:
>
>
>
> The idea is that, given (int) hash h and (int) size N, then ((long) h)
> * N) >>> 32 is a good mapping.
>
>
> I looked at this in the past weeks in a different context, and I don't
> think this would work because we have:
>
>
> That technique appears to require either a well-conditioned hash code
> (which is not the case with Integer.hashCode) or else a value of N that
> performs extra mixing on h.  (So a very *non-*power-of-two value of N
> would be better here, i.e., N with larger popcount.)
>
> A little more mixing should help the problem Florian reports with a
> badly conditioned h.  Given this:
>
> int fr(int h) { return (int)(((long)h * N) >>> 32); }
> int h = x.hashCode();
> //int bucket = fr(h);  // weak if h is badly conditioned
>
> then, assuming multiplication is cheap:
>
> int bucket = fr(h * M); // M = 0x2357BD or something
>
> or maybe something fast and sloppy like:
>
> int bucket = fr(h + (h << 8));
>
> or even:
>
> int bucket = fr(h) ^ (h & (N-1));
>
>