HashMap should be unsorted but still sorts according to key

Question

According to these:

1. http://docs.oracle.com/javase/6/docs/api/java/util/HashMap.html
2. Difference between HashMap, LinkedHashMap and TreeMap
3. java beginner : How key gets sorted in hashmaps?

The HashMap in Java should be unsorted but it is being sorted with respect to Key.

I experienced this as a problem because I needed inserted-order data. So, I used LinkedHashMap instead. But still I am confused why the HashMap sorted it.

Can anyone explain it?

I did a simple example to view the sort.

public static void main(String[] args) {

        HashMap<Integer, String> newHashMap = new HashMap<Integer, String>();
        newHashMap.put(2, "First");
        newHashMap.put(0, "Second");
        newHashMap.put(3, "Third");
        newHashMap.put(1, "Fourth");

        Iterator<Entry<Integer, String>> iterator = newHashMap.entrySet()
                .iterator();
        while (iterator.hasNext()) {

            Map.Entry<Integer, String> entry = iterator.next();
            System.out.println("Key: " + entry.getKey());
            System.out.println("Value: " + entry.getValue());
            iterator.remove();
        }

    }

Result:

Key: 0
Value: Second
Key: 1
Value: Fourth
Key: 2
Value: First
Key: 3
Value: Third

Edit:

I tried to insert 50 random numbers using Random of Java and I found some data unsorted. But, it still manages to sort most of the integers.

Random results:

...
Key: 36
Value: random
Key: 43
Value: random
Key: 47
Value: random
Key: 44
Value: random
Key: 45
Value: random
...

Answer 1

It's a coincidence (not really, rather it has to do with the hashing algorithm).

Try adding

newHashMap.put(-5, "Fifth");

as last.

Output will be

Key: 0
Value: Second
Key: 1
Value: Fourth
Key: 2
Value: First
Key: 3
Value: Third
Key: -5
Value: Fifth

The javadoc specifically says

This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time.

Answer 2

You should not infer too much! Just because three or four numbers appear sorted, it doesn't mean they have been sorted.

The hash code of a positive int is usually just that int, so if all your keys are lower than the length of the internal array the Map maintains, they may appear sorted.

Try with really big values, and you'll see that the apparing order vanishes. For example, use

100,200,300,100001, 100002, 10003, 999123456, 888777666, ....