Are the HashMap entries always sorted by key, if the key is of type Integer?

java

Solution

No, you cannot assume that entries in `HashMap` are sorted by their key, since they are not.

You probably tested a small number of entries with small `Integer` keys, which appear to be sorted, since the `hashCode` of an `Integer` is its int value itself, so key 1 goes to bin 1, key 2 goes to bin 2, etc... When you iterated over the entries, they appeared to be sorted by key, since the iteration order is according to the indices the bins.

Try large `Integer` keys and you'll see they are not sorted.

For example :

While this code produces sorted keys:

HashMap<Integer,String> map = new HashMap<> ();
for (int i=0;i<10;i++) {
  map.put (i, Integer.toString (i));
}
for (Integer key : map.keySet ()) {
  System.out.println (key);
}

Output:

0
1
2
3
4
5
6
7
8
9

This code does not:

HashMap<Integer,String> map = new HashMap<> ();
for (int i=0;i<10;i++) {
  map.put (i*100, Integer.toString (i));
}
for (Integer key : map.keySet ()) {
  System.out.println (key);
}

Output:

0
400
800
100
500
900
200
600
300
700

Problem

I am looking for a implementation, which automatically sorts its entries by key. I found the `TreeMap` implementation, which does right that. However in the tests I created, I found that entries in `HashMap` are sorted by their key, if the key is of type `Integer`, by default. Can I assume that `HashMap` works (and keeps working) like this and use it safely, or should I use `TreeMap` for that purpose?

Original source