HashMap order changes when using Thread but is constant without Thread

It's because HashMap order internally will depend on hashcode implementation.

Your Book class does not implement hashCode so it will use the default one

As much as is reasonably practical, the hashCode method defined by class Object does return distinct integers for distinct objects. (This is typically implemented by converting the internal address of the object into an integer, but this implementation technique is not required by the JavaTM programming language.)

That means it will use memory address.

In your case, it happens that for a single thread, allocated memory addresses are the same on re-run, which is not the case in threaded version.

But this is only 'by accident' and you cannot rely on it even in single threaded (someone else will run it and get a different result,or even when you run it later you can get a different result as objects will have different memory addresses)

Please ALWAYS overwrite hashCode (&equals) when using objects in hashmap.

Not really an answer but as a complement: here is the code used for the inserts (put) in the HashMap code, TreeNode code:

/** * Tie-breaking utility for ordering insertions when equal * hashCodes and non-comparable. We don't require a total * order, just a consistent insertion rule to maintain * equivalence across rebalancings. Tie-breaking further than * necessary simplifies testing a bit. */static int tieBreakOrder(Object a, Object b) {    int d;    if (a == null || b == null ||        (d = a.getClass().getName().         compareTo(b.getClass().getName())) == 0)        d = (System.identityHashCode(a) <= System.identityHashCode(b) ?             -1 : 1);    return d;}

As you can see it relies on System.identityHashCode which is native.

And in System:

/** * Returns the same hash code for the given object as * would be returned by the default method hashCode(), * whether or not the given object's class overrides * hashCode(). * The hash code for the null reference is zero. * * @param x object for which the hashCode is to be calculated * @return  the hashCode * @since   JDK1.1 */public static native int identityHashCode(Object x);

Also see this answer: How does the JVM ensure that System.identityHashCode() will never change?