Order of items in a HashMap differ when the same program is run in JVM5 vs JVM6?

Question

Hi,

I have an application which displays a collection of objects in rows, one object = one row. The objects are stored in a HashMap. The order of the rows does not affect the functionality of the application (that is why a HashMap was used instead of a sortable collection).

However I have noticed that the same aplication runs differently when run using two different versions of the Java Virtual Machine. The application is compiled using JDK 5, and can be run using either Java 5 or Java 6 runtimes, without any functional difference.

The object in question overrides java.lang.Object#hashCode() and obviously care has been taken to follow the contract specified in the Java API. This is evidenced by the fact that they always appear in the same order in every run of the application (in the same Java runtime).

For curiosity's sake, why does the choice of Java runtime affect the order?

Thanks!

Answer 1

Probably because a Map is not defined to have any particular iteration order; the order in which the elements come back is likely to be an artifact of its internal implementation and does not need to stay consistent.

If the implementation gets updated between Java 5 and 6 (especially for performance reasons), there's no benefit or obligation of Sun to make sure the iteration order stays consistent between the two.

EDIT: I just found an interesting snippet in one of the early Java 6 releases (unfortunately I'm not sure of the exact version but it's apparently HashMap 1.68 from June 2006):

 /**
  * Whether to prefer the old supplemental hash function, for
  * compatibility with broken applications that rely on the
  * internal hashing order.
  *
  * Set to true only by hotspot when invoked via
  * -XX:+UseNewHashFunction or -XX:+AggressiveOpts
  */
 private static final boolean useNewHash;
 static { useNewHash = false; }

 private static int oldHash(int h) {
     h += ~(h << 9);
     h ^= (h >>> 14);
     h += (h << 4);
     h ^= (h >>> 10);
     return h;
 }

 private static int newHash(int h) {
     // This function ensures that hashCodes that differ only by
     // constant multiples at each bit position have a bounded
     // number of collisions (approximately 8 at default load factor).
     h ^= (h >>> 20) ^ (h >>> 12);
     return h ^ (h >>> 7) ^ (h >>> 4);
 }

So it seems that despite my above assertions, Sun did in fact consider the consistency of iteration order - at some later point this code was presumably dropped and the new order made the definitive one.

Answer 2

The implementation details of HashMap can and do change. Most likely this package private method did (this is from JDK 1.6.0_16):

/**
 * Applies a supplemental hash function to a given hashCode, which
 * defends against poor quality hash functions.  This is critical
 * because HashMap uses power-of-two length hash tables, that
 * otherwise encounter collisions for hashCodes that do not differ
 * in lower bits. Note: Null keys always map to hash 0, thus index 0.
 */
static int hash(int h) {
    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

For reference, the analogue in JDK 1.5.0_06 is:

/**
 * Returns a hash value for the specified object.  In addition to 
 * the object's own hashCode, this method applies a "supplemental
 * hash function," which defends against poor quality hash functions.
 * This is critical because HashMap uses power-of two length 
 * hash tables.<p>
 *
 * The shift distances in this function were chosen as the result
 * of an automated search over the entire four-dimensional search space.
 */
static int hash(Object x) {
    int h = x.hashCode();

    h += ~(h << 9);
    h ^=  (h >>> 14);
    h +=  (h << 4);
    h ^=  (h >>> 10);
    return h;
}

Answer 3

HashMap is not married to any particular ordering, but LinkedHashMap implementation of Map should preserve the order.