Scaling problem of HashMap (introduced with alternative hashing) (original) (raw)

Peter Levart peter.levart at gmail.com
Tue Jan 1 12:53:17 UTC 2013

Hi and happy new year, 2013!

I don't know what the main purpose of "hashSeed" actually is. If it is to fight against predictable hashCode to bucket-index mappings, it does it's job somehow, but not very good. For example, it is very easy to predict the next hashSeed numbers that will be allocated:

import sun.misc.Hashing;

public class HashSeedCrack { private static final long multiplier = 0x5DEECE66DL; private static final long addend = 0xBL; private static final long mask = (1L << 48) - 1;

 static class Rnd {
     private long rnd;

     Rnd(long seed) { this.rnd = seed; }

     int nextInt() {
         rnd = (rnd * multiplier + addend) & mask;
         return (int) (rnd >>> 16);
     }
 }

 public static void main(String[] args) throws Exception {
     int r0 = Hashing.randomHashSeed(null);
     int r1 = Hashing.randomHashSeed(null);

     long s0 = ((long) r0 << 16) & mask;
     long s1 = ((long) r1 << 16) & mask;
     long mx = mask - ((1L << 16) - 1);
     Rnd rnd = null;
     for (int i = 0; i < 65536; i++) {
         long sx = s0 + i;
         if (((sx * multiplier + addend) & mx) == s1) {
             rnd = new Rnd(sx);
             int rx = rnd.nextInt();
             assert rx == r1;
             break;
         }
     }
     assert rnd != null;

     System.out.println("Next HashMap.hashSeed will be: " +

rnd.nextInt()); System.out.println("... and it is: " + Hashing.randomHashSeed(null)); } }

For this purpuse, the Hashing.randomHashSeed() should not be publicly visible. If ThreadLocalRandom is to be used instead of a private instance of a java.util.Random(), then it would defeat the "secrecy" since ThreadLocalRandom.current() is a shared per-thread instance accessible to anyone.

As far as standard ThreadLocalRandom is concerned, it's usability is impaired by it's design. It would be a better API if a plain ThreadUnsafeRandom with standard constructors was part of standard JDK API. ThreadLocal binding would then be a matter of each particular (possibly private) usage...

Regards, Peter

On 12/27/2012 08:38 PM, Aleksey Shipilev wrote:

Looks very like dumb inlined java.util.Random? Is there a security threat to use ThreadLocalRandom instead there?

-Aleksey. On 27.12.2012, at 23:16, Zhong Yu <zhong.j.yu at gmail.com> wrote:

Reported by the SO question

http://stackoverflow.com/questions/14010906 the HashMap constructor contains a CAS, which is kind of surprising. Could it be removed? transient final int hashSeed = sun.misc.Hashing.randomHashSeed(this); // CAS Zhong Yu

More information about the core-libs-dev mailing list