Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to get the 3 highest values in a HashMap?

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.

like image 482
shadwphenixx Avatar asked May 29 '20 02:05

shadwphenixx


People also ask

Can we store 3 values in HashMap?

HashMap can be used to store key-value pairs. But sometimes you may want to store multiple values for the same key.

Can a HashMap have multiple values?

A standard Java HashMap cannot store multiple values per key, any new entry you add will overwrite the previous one.


Video Answer


2 Answers

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

like image 128
PatrickChen Avatar answered Sep 24 '22 03:09

PatrickChen


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.

like image 43
Eugene Avatar answered Sep 22 '22 03:09

Eugene