For the one version of the JDK that I tried (Sun
Java 1.5.0_10), it wasn't true.
It wasn't insertion order. It wasn't alphabetical order. It wasn't ordered by value. And I only tried it with three keys -- which is the minimum size required to determine any order.
I was thinking it was some sort of implementation detail that requires lots of keys or lots of insertions and removals to break. Nothing. There is an order to the hashmap, but it is not any of those listed (and yes, the keys were Integers).
Henry