Converting HashMap to Sorted ArrayList

Question

I have a HashMap<String, Integer> containing words along with their frequencies. I need to now convert this HashMap into an ArrayList of just the words, discarding of the frequencies, but i also want the ArrayList to be sorted in descending order of words by frequency.

Does anyone know an efficient way to do this?

Solution 1

HashMap has a convenient method called entrySet(), which lets you access a collection of key-value pairs. You can use it to construct a List<Map.Entry<String,Integer>>.

Now you have something you can sort. Use a sort method with a custom comparator, which orders entries with higher frequencies toward the beginning of the list.

With a sorted list in hand, all you need to do is walk it, and harvest the words which are now in the proper order.

List<Map.Entry<String,Integer>> entries = new ArrayList<Map.Entry<String,Integer>>(
    freqMap.entrySet()
);
Collections.sort(
    entries
,   new Comparator<Map.Entry<String,Integer>>() {
        public int compare(Map.Entry<String,Integer> a, Map.Entry<String,Integer> b) {
            return Integer.compare(b.getValue(), a.getValue());
        }
    }
);
for (Map.Entry<String,Integer> e : entries) {
    // This loop prints entries. You can use the same loop
    // to get the keys from entries, and add it to your target list.
    System.out.println(e.getKey()+":"+e.getValue());
}

Demo.

Solution 2

When using Java 8 you can make use of the Stream API like follows:

final Map<String, Integer> wordStats = new HashMap<>();
// some dummy data:
wordStats.put("twice", 2);
wordStats.put("thrice", 3);
wordStats.put("once", 1);

final List<String> sortedStats = wordStats.entrySet().stream()
    .sorted(Comparator.comparing(Map.Entry::getValue, Comparator.reverseOrder()))
    .map(Map.Entry::getKey)
    .collect(Collectors.toList());
    // or to specify the list implementation:
    //.collect(ArrayList::new, ArrayList::add, ArrayList::addAll);

// Output
sortedStats.forEach(System.out::println);

Output:

thrice
twice
once

Solution 3

In Java 8 you can also do this shorter variation of what has been answered

Ascending order

ArrayList<Map.Entry<String, Integer>> sorted = newArrayList<>(frequencies.entrySet());
sorted.sort(Comparator.comparingInt(Map.Entry::getValue));

Descending order

ArrayList<Map.Entry<String, Integer>> sorted = new ArrayList<>(frequencies.entrySet());
sorted.sort(Collections.reverseOrder(Comparator.comparingInt(Map.Entry::getValue)));

Comments

[Michael]

this is a pretty standard request, you should easily be able to find stuff in the internet. Did you try something yet?

[xilpex]

Great answer, +1-- Any significance behind using final?