Image source:Wikipedia

Starting from a class loading problem

A colleague ran into a strange hashCode-related problem during development. To simplify the problem and highlight its essence, I’ve abstracted the actual business code; take a look at the code below:

C.jar:
	SomeClass.class

A.jar:
	Class.forName("SomeClass").hashCode();

B.jar:
	someClassObject.getClass().hashCode();

There is a class, let’s call it SomeClass, located in C.jar, which has an object someClassObject. A.jar uses Class.forName("SomeClass").hashCode() to get SomeClass’s hashCode, and B.jar uses someClassObject.getClass().hashCode() to get the hashCode. Both A.jar and B.jar depend on C.jar, and all three JARs run in the same JVM — that’s the context of the problem. The problem appeared when, at runtime, it turned out that the two statements returned different hashCodes!

The first instinct for this kind of problem is that the two JARs have different ClassLoaders. Later it turned out that the root cause was indeed the ClassLoader. Here is the ClassLoader hierarchy of that environment:

 Bootstrap ClassLoader
		  |
 Extension ClassLoader
		  |
Application ClassLoader
		  |
 Customize ClassLoader

The problem is: B.jar was loaded first by the Customize ClassLoader, and A.jar was loaded later by the Application ClassLoader. The SomeClass class exists in both the Application ClassLoader and the Customize ClassLoader, which caused the hashCodes to be different.

Because the underlying reason is complex, this article won’t dig into why the Customize ClassLoader didn’t delegate to the Application ClassLoader to load SomeClass. Another question raised by this problem — the implementation details of hashCode() — is the main focus of this article.

Understanding hashCode() in depth

In Java, every object has a hashCode() method, which is inherited from Object. The purpose of the hashCode() method is to support equality comparison between objects. For example, when you put an object into a HashMap, the HashMap calls the object’s hashCode() to further compute its hash value.

The hashCode() method has the following contract:

Within the same Java process, equal objects must return equal hashCode() values

However, the following views are wrong:

1. Unequal objects must have different hashCodes

2. Objects with equal hashCode() values must be equal

Here’s a question first: must the results of the following two statements be different?

Class.forName("AClass").hashCode();

Class.forName("BClass").hashCode();

From the views above we know they don’t have to be different. To understand why, we need to study the implementation details of hashCode() more deeply. Different JDK implementations may differ. Let’s look at the OpenJDK 7 implementation synchronizer.cpp

static inline intptr_t get_next_hash(Thread * Self, oop obj) {
  intptr_t value = 0 ;
  if (hashCode == 0) {
     // This form uses an unguarded global Park-Miller RNG,
     // so it's possible for two threads to race and generate the same 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 addrBits = intptr_t(obj) >> 3 ;
     value = addrBits ^ (addrBits >> 5) ^ GVars.stwRandom ;
  } else
  if (hashCode == 2) {
     value = 1 ;            // for sensitivity testing
  } else
  if (hashCode == 3) {
     value = ++GVars.hcSequence ;
  } else
  if (hashCode == 4) {
     value = 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 &= markOopDesc::hash_mask;
  if (value == 0) value = 0xBAD ;
  assert (value != markOopDesc::no_hash, "invariant") ;
  TEVENT (hashCode: GENERATE) ;
  return value;
}

In the comment for hashCode==0, it clearly says:

so it's possible for two threads to race and generate the same RNG.

In a multi-threaded environment, if the hashCode=0 hash generation algorithm is used, two different classes are entirely capable of generating the same hash value.

We can control the hashCode() generation algorithm via the Java startup parameter -XX:hashCode=n (from 0 to 5). The algorithms corresponding to 0 through 5 are:

0 – Park-Miller RNG (default)  Park-Miller random number generator
1 – function of address and some global state
2 – const 1
3 – sequential counter
4 – address of an object
5 – thread specific xor-shift

Each option uses a different algorithm to generate the object’s hash value. The Park-Miller random number generation algorithm can be referenced at Lehmer random number generator. The fourth algorithm directly uses the object’s memory address as the hash value. For the other algorithms, this article won’t explore them further.

• Tags:
• Java
• JVM
• HashCode