Understanding hashCode in Java

There are already plenty of articles about hashCode. I am writing this one mainly to record it in my own order.

What is hashCode?

The implementation of hashCode on Object is a native method that produces a characteristic value for the current object instance:

public native int hashCode();

The exact implementation can vary by JVM. In JDK 1.8, the get_next_hash function that actually calculates the hash code is implemented as follows (src/share/vm/runtime/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;
}

With hashCode set to 4, the memory address is used directly. The default is the random algorithm used when hashCode >= 5; this can be changed with the JVM parameter -XX:hashCode.

I looked it up: the xor-shift scheme was invented by George Marsaglia at Florida State University. It generates random numbers using shifts and XOR operations, which are fast on a computer because shift instructions need fewer machine cycles. If you are interested, it is worth digging into further.

hashCode and equals

hashCode comes from a hash function, so different objects can produce the same hash value. It is like having two different strings with the same MD5 value, while there may be other unknown strings with that same value as well.

So objects with the same hash code are not necessarily equal; equals is still needed to compare them. If two objects are true according to equals, their hash codes must be the same.

Two objects having the same hash code does not prevent them from being keys in a HashMap. Even if they land in the same bucket, comparing the keys themselves distinguishes them.

equals must satisfy several properties: reflexivity, symmetry, transitivity, and consistency.

Symmetry: if x.equals(y) returns true, y.equals(x) should also return true.
Reflexivity: x.equals(x) returns true.
Transitivity: if x.equals(y) and y.equals(z) both return true, then z.equals(x) returns true.
Consistency: if x.equals(y) returns true, it must keep returning true while the contents of x and y do not change.

This is easy to understand if you think of comparing two numbers: these properties are simply what equality should mean.

To decide that objects are equal, equals must be overridden; otherwise the implementation on Object is used.

Why does overriding equals usually mean overriding hashCode as well? Suppose there is a class Apple with color and weight fields. Comparing two instances, A and B, for equality (and one might not be an Apple at all) is really a comparison of both fields. If hashCode is not overridden and a new instance C is created with the same color and weight as B, B.equals(C) and their different hash codes become confusing.

The classic way to override hashCode uses 17 and 31:

public class Apple {
    private String color;
    private int weight;

    @Override
    public boolean equals(Object o) {
        if (o == this) return true;
        if (!(o instanceof Apple)) {
            return false;
        }
        Apple apple = (Apple) o;
        return apple.color.equals(color) &&
                apple.weight == weight;
    }

    @Override
    public int hashCode() {
        int result = 17;
        result = 31 * result + color.hashCode();
        result = 31 * result + weight;
        return result;
    }
}

You can also use java.util.Objects to implement equals and hashCode, or Apache Commons Lang’s EqualsBuilder and HashCodeBuilder. Both approaches package the same 17-and-31 idea.

Hash codes for collections

AbstractSet adds the integer hash code of every element. Two HashSets that both contain "a", "b", and "c" therefore have the same hash code regardless of insertion order:

public int hashCode() {
        int h = 0;
        Iterator<E> i = iterator();
        while (i.hasNext()) {
            E obj = i.next();
            if (obj != null)
                h += obj.hashCode();
        }
        return h;
    }

AbstractList uses 31 to spread the result out more:

public int hashCode() {
        int hashCode = 1;
        for (E e : this)
            hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());
        return hashCode;
    }

AbstractMap iterates over its entries and adds their hash codes, and so on.

If two collections have the same hash code, that says nothing conclusive about whether they are equal. If their hash codes differ, they are definitely not equal. This can be used as a quick way to rule out equality.

Caching an object’s hashCode

hashCode is calculated each time. Although it is a native method and very fast, caching can be considered when it is used repeatedly in large numbers, much as Integer caches objects for values from -128 to 127.

Originally published on SegmentFault.