How to get the 3 highest values in a HashMap?

Question

I have a hashmap which is the following:

    HashMap<String, Integer> hm = new HashMap<String, Integer>;
    hm.put("a", 1);
    hm.put("b", 12);
    hm.put("c", 53);
    hm.put("d", 2);
    hm.put("e", 17);
    hm.put("f", 8);
    hm.put("g", 8);

How would I get the keys which have the 3 highest values? So it would return:

    "c", "e", "b"

Thanks.

Answer 1

My solution, sort by values and get top 3 and return key list.

List<String> keys = hm.entrySet().stream().sorted(Map.Entry.<String, Integer>comparingByValue().reversed()).limit(3).map(Map.Entry::getKey).collect(Collectors.toList());

Hope it helps

Answer 2

This is a lot harder to read, but will perform a lot better:

 public static List<String> firstN(Map<String, Integer> map, int n) {
    PriorityQueue<Entry<String, Integer>> pq = new PriorityQueue<>(
        n + 1, Map.Entry.comparingByValue()
    );

    int bound = n + 1;
    for (Entry<String, Integer> en : map.entrySet()) {
        pq.offer(en);
        if (pq.size() == bound) {
            pq.poll();
        }
    }

    int i = n;
    String[] array = new String[n];
    while (--i >= 0) {
        array[i] = pq.remove().getKey();
    }
    return Arrays.asList(array);
}

If you know how a PriorityQueue works, this is rather trivial: it keeps only n + 1 elements at any given point in time. As elements are being added, the smallest element is removed, one by one.

When this is done, we insert elements into an array, but in reverse order (because a PriorityQueue keeps sorted only its head or the head is always max/min according to the Comparator).

You can even make this generic, or create a custom collector with streams for this.

Answer 3

Here's my take on it: This keeps track of only the top n items in a TreeSet.

import java.util.*;
import java.util.stream.Collectors;

public class TopN {
    public static <E> Collection<E> topN(Iterable<E> values, Comparator<? super E> comparator, int n) {
        NavigableSet<E> result = new TreeSet<>(comparator.reversed());
        for (E value : values) {
            result.add(value);
            if (result.size() > n) {
                result.remove(result.last());
            }
        }
        return result;
    }

    public static void main(String[] args) {
        Map<String, Integer> hm = Map.of(
                "a", 1,
                "b", 12,
                "c", 53,
                "d", 2,
                "e", 17,
                "f", 8,
                "g", 8);

        List<String> result = topN(hm.entrySet(), Map.Entry.comparingByValue(), 3)
                .stream()
                .map(Map.Entry::getKey)
                .collect(Collectors.toList());
        System.out.println(result);
    }
}

The final output is [c, e, b]