On Generating Identity Hash Codes

Generation Strategies
Park–Miller/Lehmer RNG
OOPs Based
Static Number
Sequential Numbers
Marsaglia’s Xor-Shift
Good Hashcodes
Conclusion

This simple piece of code probably prints one of the most misunderstood outputs in Java:

System.out.println(new Object());

And that output would be:

java.lang.Object@69663380

What does that part after @ represent? Is this the memory address of the object? Is it the hashcode? How about both? or even none?

Over the course of this article, we’re going to see how the HotSpot JVM generates this value and what it represents. so, Let’s get started then!

Generation Strategies

As of this writing, HotSpot JVM has a few different strategies to generate hashcodes:

static inline intptr_t get_next_hash(Thread* self, oop obj) {
  intptr_t value = 0;
  if (hashCode == 0) {
    // This form uses global Park-Miller RNG.
    // On MP system we'll have lots of RW access to a global, so the
    // mechanism induces lots of coherency traffic.
    value = os::random();
  } else if (hashCode == 1) {
    // This variation has the property of being stable (idempotent)
    // between STW operations.  This can be useful in some of the 1-0
    // synchronization schemes.
    intptr_t addr_bits = cast_from_oop<intptr_t>(obj) >> 3;
    value = addr_bits ^ (addr_bits >> 5) ^ GVars.stw_random;
  } else if (hashCode == 2) {
    value = 1;            // for sensitivity testing
  } else if (hashCode == 3) {
    value = ++GVars.hc_sequence;
  } else if (hashCode == 4) {
    value = cast_from_oop<intptr_t>(obj);
  } else {
    // Marsaglia's xor-shift scheme with thread-specific state
    // This is probably the best overall implementation -- we'll
    // likely make this the default in future releases.
    unsigned t = self->_hashStateX;
    t ^= (t << 11);
    self->_hashStateX = self->_hashStateY;
    self->_hashStateY = self->_hashStateZ;
    self->_hashStateZ = self->_hashStateW;
    unsigned v = self->_hashStateW;
    v = (v ^ (v >> 19)) ^ (t ^ (t >> 8));
    self->_hashStateW = v;
    value = v;
  }

  value &= markWord::hash_mask;
  if (value == 0) value = 0xBAD;
  assert(value != markWord::no_hash, "invariant");
  return value;
}

As shown above, the hashcode generation strategy is determined by a mysterious and yet well-named hashCode variable. Let’s see where does this variable come from:

experimental(intx, hashCode, 5, "(Unstable) select hashCode generation algorithm")

So this hashCode variable is actually an experimental tuning flag with a default value of 5:

$ java -XX:+UnlockExperimentalVMOptions -XX:+PrintFlagsFinal -version | grep hashCode
intx hashCode          = 5          {experimental} {default}

Put simply, we can use the -XX:+UnlockExperimentalVMOptions -XX:hashCode=<i> combination of tunables to change the strategy.

Now let’s see how each strategy works.

Park–Miller/Lehmer RNG

The first hashcode generation approach uses one of the most common random number generation strategies: a class of linear congruential generator (LCG) algorithms known as Lehmer RNG or even Park–Miller RNG:

static inline intptr_t get_next_hash(Thread* self, oop obj) {
  intptr_t value = 0;
  if (hashCode == 0) {
    // This form uses global Park-Miller RNG.
    // On MP system we'll have lots of RW access to a global, so the
    // mechanism induces lots of coherency traffic.
    value = os::random();
  }
  // omitted
}

This algorithm starts with an initial seed value, $X_{0}$ . Then generates each random variable from the previous one as following:

X_{n + 1} = (a X_{n} + c) m o d m

Let’s take a look at the os::random() defintion:

volatile unsigned int os::_rand_seed = 1;
int os::random() {
  // Make updating the random seed thread safe.
  while (true) {
    unsigned int seed = _rand_seed;
    unsigned int rand = random_helper(seed);
    if (Atomic::cmpxchg(&_rand_seed, seed, rand) == seed) {
      return static_cast<int>(rand);
    }
  }
}

The os::random() tries to generate a random number from the global _rand_seed variable and then update that seed atomically.

When multiple threads try to change the seed, only one of them can successfully change the seed and the cmpxchg will fail for others. Losing threads will retry the same operation until they succeed.

Therefore, in the presence of high contention, the rate of CAS failures will increase, hence this comment:

// On MP system we'll have lots of RW access to a global, so the
// mechanism induces lots of coherency traffic.

Quite interestingly, this high contention happens when a lot of objects are trying to generate their hashcode for the first time. This doesn’t seem to be a contention point from the Java perspective. However, with the -XX:hashCode=0 this contention exists under the hood.

OOPs Based

The second and fifth strategies are using a function of memory address as the hashcode:

else if (hashCode == 1) {
    // This variation has the property of being stable (idempotent)
    // between STW operations.  This can be useful in some of the 1-0
    // synchronization schemes.
    intptr_t addr_bits = cast_from_oop<intptr_t>(obj) >> 3;
    value = addr_bits ^ (addr_bits >> 5) ^ GVars.stw_random;
}
else if (hashCode == 4) {
    value = cast_from_oop<intptr_t>(obj);
}

So if we use either of -XX:hashCode=1 or -XX:hashCode=4, the hashcode will depend on the memory address.

Static Number

Probably the coolest, least useful, and most efficient strategy is the third one:

else if (hashCode == 2) {
    value = 1;            // for sensitivity testing
}

Which generates 1, all the time!

If we run the same snippet with -XX:+UnlockExperimentalVMOptions -XX:hashCode=2:

System.out.println(new Object());

Then it will print:

java.lang.Object@1

So the part after @ is always hashcode, at least! I’m guessing they’re using this strategy as a benchmark baseline. It’s just a guess, though. If that’s true, then this strategy ain’t that useless after all.

Sequential Numbers

The fourth strategy is basically an auto-increment for hashcode generation:

struct SharedGlobals {
  // omitted
  DEFINE_PAD_MINUS_SIZE(1, DEFAULT_CACHE_LINE_SIZE, sizeof(volatile int) * 2);
  // Hot RW variable -- Sequester to avoid false-sharing
  volatile int hc_sequence;
  DEFINE_PAD_MINUS_SIZE(2, DEFAULT_CACHE_LINE_SIZE, sizeof(volatile int));
};
static SharedGlobals GVars;

// omitted
else if (hashCode == 3) {
    value = ++GVars.hc_sequence;
}

If we run the following code with -XX:+UnlockExperimentalVMOptions -XX:hashCode=3, we will probably see some consequetive hashcodes:

System.out.println(new Object().hashCode()); // prints 317
System.out.println(new Object().hashCode()); // prints 318
System.out.println(new Object().hashCode()); // prints 319

Marsaglia’s Xor-Shift

As of this writing, if we pass anything more than 4 as the value of -XX:hashCode, this random number generator will be used:

else {
    // Marsaglia's xor-shift scheme with thread-specific state
    // This is probably the best overall implementation -- we'll
    // likely make this the default in future releases.
    unsigned t = self->_hashStateX;
    t ^= (t << 11);
    self->_hashStateX = self->_hashStateY;
    self->_hashStateY = self->_hashStateZ;
    self->_hashStateZ = self->_hashStateW;
    unsigned v = self->_hashStateW;
    v = (v ^ (v >> 19)) ^ (t ^ (t >> 8));
    self->_hashStateW = v;
    value = v;
}

The implementation seems a bit complicated. However, the idea is simple. Instead of using some global shared mutable state as the seed, this is using a thread-specific state to generate the random number. Therefore, it will outperform the os::random() and the sequential approach, as there is no need for thread synchronization.

Currently, this is the default hashcode generation strategy.

Good Hashcodes

A hashcode implementation is a good one if it exhibits both uniform distribution and good performance. Let’s evaluate each strategy with respect to these parameters:

The os::random() approach has good uniformity and randomness. However, it won’t perform that well in highly contended environments
The memory address based approach usually won’t exhibit uniform distribution, which is very critical for hashcodes
The one that always returns 1 is fun!
The Marsaglia’s Xor-Shift generates random numbers with good distribution and also, good performance

Here’s a benchmark result from Aleksey Shipilëv:

32 threads:
-XX:hashCode=0: 10.7 +- 0.1 ops/usec
-XX:hashCode=1: 175.2 +- 4.9 ops/usec
-XX:hashCode=2: 184.8 +- 3.7 ops/usec
-XX:hashCode=3: 14.2 +- 0.1 ops/usec
-XX:hashCode=4: 160.0 +- 2.6 ops/usec
-XX:hashCode=5: 176.6 +- 6.0 ops/usec

Conclusion

Just to recap, the part after @ is definitely the identity hashcode.

The hashcode itself is usually a random number but can also be a function of the memory address. The identity hashcode, in the HotSpot JVM, consumes at most 31 bits of the object header, while the memory address may be up to 64 bits (without compressed references). Therefore, the hashcode may not be equal to the memory address, even though it can be a function of it!

Before wrapping up, it’s worth taking a look at this mailing list on the same topic.