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

Question

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?

Answer 1

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