Java Hashmap is automatically sorted

Question

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

public class Main
{
    public static void main(String[] args) {
        
        Map<String, String> map = new HashMap<String, String>();
        
        map.put("Str1", "value1");
        map.put("Str2", "value2");
        map.put("Str3", "value3");
        map.put("Str4", "value4");
        map.put("Str5", "value5");
        
        System.out.println(map.entrySet());
        
        Collection<String> values = map.values();
        String[] arr = values.toArray(new String[0]);
        System.out.println(arr[3]);
    }
}

I know Hashmap has no order but this code keeps showing [Str5=value5, Str4=value4, Str3=value3, Str2=value2, Str1=value1] value2 Is there anything that I'm missing?

There's a difference between "unordered" and "not having a defined order". — Robby Cornelissen, Oct 04 '22 at 08:54
Change the construction from `new HashMap()` to either `new HashMap<>(4, 2f)` or `new HashMap<>(2, 4f)` and see what happens. Or try to add all values from `"Str1"` to `"Str9"`. — Holger, Oct 04 '22 at 11:04
The order of iteration is undefined but it is not random. Therefore, it is reasonable that is is consistent **if** the Map is unperturbed between iterations. However, the the order of iteration can/will change dramatically if you add or remove elements from the Map. — vsfDawg, Oct 04 '22 at 11:09
For other visitors: `SortedMap map = new TreeMap<>();` would keep the keys sorted. And with `SortedMap ` you can do `map.subMap("D", "E")` for all keys starting with "D". — Joop Eggen, Oct 05 '22 at 08:29

Persixty · Answer 1 · 2022-10-05T10:40:52.310

This is an artefact of how String.hashCode() is implemented.

Add this code:

    System.out.println(map.entrySet());
    
    for(Map.Entry<String,String> curr : map.entrySet()){
        String str=curr.getValue();
        System.out.println(str+" "+str.hashCode());
    }

Typical Output:

value5 -823812892
value4 -823812893
value3 -823812894
value2 -823812895
value1 -823812896

Hang on! Those hash-codes are sequential. Just because hash-code is 'arbitrary' that doesn't mean there's no structure to it.

It turns out that the standard implementation is calculated as a 'multiply and add' calculation (where h is the hash-code):

for (int i = 0; i < chars.length; i++) {
    h = 31 * h + chars[i];
}

And because those strings only differ in their last character and that character is sequential between them the hash-code comes out in order.

The effect of the last character is just an add.

The sequencing is not an intended property of the hash-code. It's just the way those values fall.

Further it means the way those strings happen to get placed in the hash-table is also by coincidence sequential. So when the entries are iterated in arbitrary (but in practice 'happen to be') order they come ordered as shown.

That ordered outcome is pure accident. Add further values and the pattern will eventually break. Refer to the proposed 'duplicate' answers for more detail about how HashMap is implemented.

Java Hashmap is automatically sorted

1 Answers1