CODEWITHSUNDEEP
javacollections
David Landup
David Landup

Reputation: 168

Why does Java *sort* HashMap entries even though it shouldn't?

A HashMap in Java shouldn't be sorted, and doesn't guarantee order. Its order can be changed throughout the lifecycle of the application and if you want a sorted map, you should use a LinkedHashMap, or better yet, a TreeMap.

I know this, have experienced this, and this is confirmed by the official documentation.

However, I've just wrote some code that just won't keep the HashMap unsorted. At first, I thought it was fluke coincidence, but I ran the code many times and the same output is shown.

Map<String, Double> map = new HashMap<>();

map.put("A", 99.5);
map.put("B", 67.4);
map.put("C", 67.4);
map.put("D", 67.3);

System.out.println("Unsorted map: " + map);

This results in:

Unsorted map: {A=99.5, B=67.4, C=67.4, D=67.3}

I assumed that the String keys got sorted lexicographically, somehow, since they followed A, B, C and D, though, here's another example where the sorted String keys aren't necessarily sorted by lexicographical value:

Map<String, Integer> unsortedMap = new HashMap();

unsortedMap.put("David", 21);
unsortedMap.put("Scott", 34);
unsortedMap.put("Marcus", 31);
unsortedMap.put("Vladimir", 24);

unsortedMap.entrySet().forEach(System.out::println);

And this one results in:

Marcus=31
David=21
Vladimir=24
Scott=34

Marcus is lexicographically greater than David, but David is lexicographically less than Vladimir.

I assume that this part of the source code specifically is responsible for this:

static int tieBreakOrder(Object a, Object b) {
    int d;
    if (a == null || b == null ||
        (d = a.getClass().getName().
         compareTo(b.getClass().getName())) == 0)
        d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
             -1 : 1);
    return d;
}

Note: I'm running Java 15, though, rolling back to older versions, such as Java 8 didn't change the behavior at all.

Upvotes: 2

Views: 111

Answers (1)

Daniel
Daniel

Reputation: 680

You're right with assuming String keys got sorted - but it is not lexicographically sorted but based on hash of the key.
Method java.util.HashMap#put uses method java.util.HashMap#hash for calculating hash of key - String in our case.
Results of java.util.HashMap#hash for letter A - 65, letter B - 66, letter C - 67 and so on up for single-letter objects (checked for A-Za-z, can't say anything about other values). Result of java.util.HashMap#hash for David - 65805752.

Calculated hash is then used to decide the index of bucket in underlying array java.util.HashMap#table in the method java.util.HashMap#putVal. Exact part of code:

p = tab[i = (n - 1) & hash]

Which effectively takes proper index of array based on hash value.

So, yeah - order of entries not guaranteed - but it can be manipulated by knowing the exact size of underlying array of nodes and knowing hashcode of keys that are to be put into map

Upvotes: 3

Related Questions