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, ....

Answer 3

You can't assume that it will be sorted. The reason why it appears sorted, in this simple example: A HashMap is internally constructed from "Bins". These Bins contain the actual elements. They are basically small lists that reside in an array.

[0] -> [ Bin0: ... ]
[1] -> [ Bin1: ... ]
[2] -> [ Bin2: ... ]
[3] -> [ Bin3: ... ] 

When an item is inserted into the HashMap, then the "Bin" in which it should be inserted is - to simplify it a little - found by using the hashCode() of the object as an array index. For example, if the hashCode is 2, it will be inserted into Bin 2. When this "index" is greater than the array size, it will be placed into Bin (index%arraySize) - that is, if the hashCode is 5, it will be inserted into Bin 1.

And since a HashMap initially has an internal array size of 10, inserting Integer objects between 0 and 9 will coincidentally place the elements in the right order into the array. (The hashCode of an Integer is just its value, of course).

(Note: The actual algorithms and hash functions may be slightly more complicated, but that's the basic idea)

Answer 4

It's pure coincidence. Sometimes it appears to be sorted, but keep adding keys and the dream will shatter.

I wrote this little program:

import java.util.Map;
import java.util.HashMap;

class MapTest {

    public static void main(String[] args){
        int count = Integer.parseInt(args[0]);
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i = 0; i < count; i++) map.put(i, i);
        System.out.println(map);
    }

}

When running java MapTest 20, I get the following output (line-wrapped for readability):

{0=0, 1=1, 2=2, 3=3, 4=4, 5=5, 6=6, 7=7, 8=8, 9=9, 10=10, 11=11, 12=12, 13=13, 
14=14, 15=15, 17=17, 16=16, 19=19, 18=18}

It's simply a property of the implementation of HashMap that Integers added sequentially (and starting at 0) at first seem to be ordered.

Answer 5

Like every one is saying (AND is right about) is that you should assume that the keys in an HashMap are not sorted. Now they LOOK sorted in your case for two simple reasons:

1 - You are using Integer as a key: The HashMap use the hashCode() method of the Object class of Java to find the index in the underlying array it uses to store the Entry instances (what contains your values and keys in the HashMap). It just so happen that the hashcode of an Integer is its own value.

2 - You are not setting the initial size of the HashMap and thus are using its default initial size (which is 16). So until you add a key below 0 or above 16 (included) you will see the keys stored in order. Since the HashMap gets the index by doing

int index = newKey.hashCode() % this.capacity;

Later on HashMap might increase the capacity of its underlying array if you insert a lot key-value pairs (how and when it decides to do that is very interesting if you are into algo and data structure study), so you might end up in a situation in which your Integer keys might look sorted again, but they actually are not intentionally sorted.

Btw if your keys are going to be Integers and you can estimate the maximum key value you are going to have I'd suggest to directly use an array. Access is faster and the memory used will be the same or slightly less.

Answer 6

I would recommend you to use a LinkedHashMap. In the LinkedHashMap the elements can be accessed in their insertion order.

Answer 7

You can't make assumptions about the orderings on HashMap objects. They will order as they please, implementation-defined. You should treat them as unordered data structures.

Answer 8

Actually It can not be ensured the order.

Hashmap uses hashcode to hash data for search fast.

Your key is so simple, so it sorted.

Answer 9

Mine is an educated guess, but the reason is likely to be the fact that the default hashCode method uses the memory location. The memory location of small Integers (and your keys are autoboxed into Integer) are most likely fixed: it would be nonesense to have Integer.valueOf(1) return a different memory location on multiple calls. Finally, most likely these fixed memory locations are in the ascending order. This would explain this coincidence, but well, one would need to dig into the implementation of Integer and HashMap to prove this.

Correction: in case of Integer "A hash code value for this object, equal to the primitive int value represented by this Integer object." (JavaDoc). Which, although a different number, confirms the idea.

Answer 10

Since no answer really utilized looking at the Java source, I will do so! :)

When you call the put() function, the internal hash function uses the hashCode of the object, to generate the hashing index. [put() source]

The hash() function simply ensures that hashCodes that differ only by constant multiples at each bit position have a bounded number of collisions [use Google to see why that is the case].

Things just coincidentally worked here. That is about it.

Answer 11

Questioner said:
"The HashMap in Java should be unsorted but it is being sorted with respect to Key."
Yes, correct. I will show you with bellow sample

Map<String, String> map1 = new HashMap<String, String>();
map1.put("c","xxxx");
map1.put("b","yyyy");
map1.put("a","zzzz");
for (String key :map1.keySet())
  System.out.println(map1.get(key));

System.out.println();

Map<Integer,String> map2 = new HashMap<Integer,String>();
map2.put(3,"xxxx");
map2.put(2,"yyyy");
map2.put(1,"zzzz");
for (int key :map2.keySet())
  System.out.println(map2.get(key));

Output shows HashMap use Key to sort data

xxxx
yyyy
zzzz

zzzz
yyyy
xxxx