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.

If you want ordering you shouldn't be using a hash map in the first place. Use an ordered map such as `TreeMap`. — user207421, May 29 '20 at 03:13

score 12 · Accepted Answer · answered May 29 '20 at 02:39

12

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

answered May 29 '20 at 02:39

PatrickChen

1,350
1
11
19

2

That would work well for relatively small input maps (< 10000 elements). It would be better to use some sort of collector that would keep track of the current top three, so that you don't have to sort the entire map. – Daniel May 29 '20 at 02:44
@Daniel [here you go](https://stackoverflow.com/a/62078310/1059372) – Eugene May 29 '20 at 03:41

Eugene · Answer 2 · 2020-05-29T03:54:39.830

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.

score 1 · Answer 3 · answered Jun 01 '20 at 02:18

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]

How to get the 3 highest values in a HashMap?

3 Answers3