Efficient way to sort keys of hashmap Java

Question

Given a hashMap and return the keys of hashmap in sorted order in arraylist This is the function API:

ArrayList<String> foo(HashMap<String,String> hashMap)
{
}

Now, there are two ways to solve problem:

Take all keys in arraylist and then sort it

Store the keys of map in treeset and then store in arraylist and return.

Former approach will not uses additional space complexity as i am not using treeset. The keys are alphanumeric. Which one will have less time complexity. Any other way you would recommend?

http://stackoverflow.com/questions/109383/sort-a-mapkey-value-by-values-java or http://stackoverflow.com/questions/109383/sort-a-mapkey-value-by-values-java — Dev. Joel, Sep 21 '16 at 04:55
This is actually an hackerrank question. So, I cant change the API — ojas, Sep 21 '16 at 05:37
@ojas I've always wondered why people come on SO with Project Euler and Hackerrank questions. Aren't you supposed to solve them by yourself, thereby making you the "hacker" (or Euler I guess?). Or is the idea that it'll be helpful in your CV to have "I have 123 points on hackerrank"? — Kayaman, Sep 21 '16 at 06:40
I have solved with both techniques. I came here just for a suggestion to know people views about efficiency so that i can apply those knowledge in upcoming problems — ojas, Sep 21 '16 at 09:00

GhostCat · Answer 1 · 2016-09-21T05:29:04.237

To a certain degree that depends on what you intend to do with the "sorted" thingy afterwards.

But in your case, you are saying: in the end, you want a sorted list; thus: directly create that a list, sort and return it!

Even when both approaches have the same complexity (O(n*log(n)) - keep in mind that sorting that list can be probably faster (because it just has to move elements in an array, instead of having to create lots of tree nodes).

In other words: creating that TreeList to then turn it into an ArrayList means for sure a lot of copying will go on. Simply avoid that!

sprinter · Accepted Answer · 2016-09-21T05:42:03.540

The answer is going to depend on the domain of the keys. There are some situations in which storing the keys in a sorted order (i.e. in a tree) is very efficient. However I would suggest in most cases it will be more efficient to sort once, on retrieval.

I tried the following code:

    Map<Integer, Integer> map = new HashMap<>();
    Random random = new Random();
    random.ints(1000000).forEach(n -> map.put(n, n));
    long time1 = System.currentTimeMillis();
    Set<Integer> set = new TreeSet<>(map.keySet());
    List<Integer> list1 = new ArrayList<>(set);
    long time2 = System.currentTimeMillis();
    List<Integer> list2 = new ArrayList<>(map.keySet());
    Collections.sort(list2);
    long time3 = System.currentTimeMillis();
    System.out.println("Set approach " + (time2 - time1));
    System.out.println("Sort approach " + (time3 - time2));

The result was 3768 and 1824 which I suspect would be fairly typical of the two approaches.

As a matter of interest I also tried:

   List<Integer> list3 = map.keySet().stream().sorted().collect(Collectors.toList());

The result was 537 milliseconds: more than 3 times faster than the Collections.sort approach.

However when I retried with 10 million entries, the three approaches took

26,916 for TreeSet
2,845 for Collection.sort
13,580 for Stream.sorted

The conclusion is that sorting the array once is much more efficient for largish maps.

Efficient way to sort keys of hashmap Java

2 Answers2