Best way to iterate through HashMap<Integer,X> when you need sorted by keys

I have a code as below:

private final HashMap<Integer, X> map = new HashMap<>();

I need to convert HashMap entries into List of some DTOs(based both on key and value from map). I also need it to be sorted by keys.

I noticed that since my keys are Integers I can access it just through:

map.forEach(..);

and the order witholds. Is it the most efficient way? Or are there any better apporaches?

In that case I care more about efficiency than clean code.

EDIT:
I do not want to use TreeMap because I also need O(1) and NOT O(Log(N) for inserts.

IYou said:

>I noticed that since my keys are Integers I can access it just through:
>
>map.forEach(..);
>
>and the order witholds.

That you saw a few numbers appear in sorted order was mere luck, not true sorting. The Map interface, and the HashMap class, clearly state in their Javadoc that they do not iterate with any particular order.

That means you should not rely on any apparent ordering. Even if the current implementation did happen to use an ordering internally, the implementation is free to change in a future version to a different sort or arbitrary order, thereby breaking your app.

👉 If you want sorted order, you must pay for sorting. You can either pay early or pay later, your choice.

Pay early

Pay early by using a NavigableMap (or SortedMap) that maintains your entries in the order of their keys.

The TreeMap class is one implementation of those interfaces. If you need concurrency, ConcurrentSkipListMap is another.

private final NavigableMap<Integer, X> map = new TreeMap<>();

Pay later

Pay later by first populating your Map such as HashMap. When the map is complete, sort.

• You can sort by using Stream as seen in the smart Answer by WJS.
• Or you can sort by building a NavigableMap from your Map.

private final Map<Integer, X> map = new HashMap<>();
…
private final NavigableMap<Integer, X> navMap = new TreeMap<>( map ) ;

A full example.

Map < Integer, String > map =
        Map.of(
                3 , "Carol" ,
                1 , "Alice" ,
                2 , "Bob"
        );
NavigableMap < Integer, String > navMap = new TreeMap <>( map );

System.out.println( "map = " + map );
System.out.println( "navMap = " + navMap );

When run, notice how map prints with an order different than creation order. In contrast, navMap always prints in key-sorted order.

map = {2=Bob, 1=Alice, 3=Carol}
navMap = {1=Alice, 2=Bob, 3=Carol}

Or, in your case, you are producing a List that you want in a certain order. You can pay later by producing the list in non-sorted order, then sort that list. You can either sort by natural order or sort by specifying a Comparator.

Collections.sort( list ) ;

You said:

>I do not want to use TreeMap because I also need O(1) and NOT O(Log(N) for inserts.

Beware of premature optimization. Unless you have huge numbers of elements, or frequently repeat this code, I would be surprised to find any significant impact. Perform some benchmarking or profiling rather than assume a performance bottleneck.

>I need to convert HashMap entries into List of some DTOs(based both on key and value from map). I also need it to be sorted by keys.

Whether you sort during insertion using a TreeMap, or later is up to you but you will still need to sort and incur the cost. But to address your question, here is an alternative.

• declare the DTO (here I'm using a record)
• stream the map entrySet
• sort on the key create each DTO, return them in a list.

record DTO<X>(Integer getInt, X getX) {}
Map<Integer, String> map = new HashMap<>(); // populated with the data
List<DTO<String>> list = map.entrySet().stream()
        .sorted(Entry.comparingByKey())
        .map(e -> new DTO<String>(e.getKey(), e.getValue()))
        .toList();

The above returned list will be immutable. You can also change .toList() to return a specific type of collection. Here is one returning an ArrayList.

.collect(Collectors.toCollection(ArrayList::new));

</details>