ojas ojas - 10 months ago 42
Java Question

Efficient way to sort keys of hashmap Java

Given a

and return the keys of
in sorted order in

This is the function API:

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

Now, there are two ways to solve problem:

  1. Take all keys in arraylist and then sort it

  2. 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?


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());
    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.