Ordering of elements in Java HashSet

@Behrang's answer is good but to be more specific, the only reason why the HashSet seems to be in the same order as the LinkedHashSet is that integer.hashCode() happens to be the integer value itself so the numbers happen to be in order in the HashSet internal storage. This is highly implementation specific and as @Behrang says, really a coincidence.

For example, if you use new HashSet<>(4) which sets the initial number of buckets to be 4 (instead of 16) then you might have gotten the following output:

HashSet<Integer> hi = new HashSet<Integer>(4);
...
[3, 4, 5, 6, 7, 8, 9]
[8, 9, 3, 4, 5, 6, 7]
[8, 9, 3, 4, 5, 6, 7]

If you had stuck in values >= 16, you might get something like this:

Integer[] j = new Integer[] { 3, 4, 5, 6, 7, 8, 9, 16 };
...
[3, 4, 5, 6, 7, 8, 9, 16]
[16, 3, 4, 5, 6, 7, 8, 9]
[16, 3, 4, 5, 6, 7, 8, 9]

The second one (just using HashSet) is only a coincidence. From the JavaDocs:

This class implements the Set interface, backed by a hash table (actually a HashMap instance). It makes no guarantees as to the iteration order of the set; in particular, it does not guarantee that the order will remain constant over time. This class permits the null element.

The third one (LinkedHashSet) is designed to be like that:

Hash table and linked list implementation of the Set interface, with predictable iteration order. This implementation differs from HashSet in that it maintains a doubly-linked list running through all of its entries. This linked list defines the iteration ordering, which is the order in which elements were inserted into the set (insertion-order). Note that insertion order is not affected if an element is re-inserted into the set. (An element e is reinserted into a set s if s.add(e) is invoked when s.contains(e) would return true immediately prior to the invocation.)