ArrayList<String> foo(HashMap<String,String> hashMap)
- Take all keys in arraylist and then sort it
- Store the keys of map in treeset and then store in arraylist and return.
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
However when I retried with 10 million entries, the three approaches took
The conclusion is that sorting the array once is much more efficient for largish maps.