Java find multiple lowest key/value pairs in a hashmap

Question

I have a small HashMap (less than 100 entries) that contains a unique object (of my design) as the key and a Double as the value.

I need to retrieve n number of objects that have the lowest values.

So say my HashMap looked like this and I wanted the lowest 3.

Object, 4.0

Object, 5.0

Object, 2.0

Object, 12.0

Object, 10.0

Object, 3.0

I would want to fetch the first, third, and last entries as those have the lowest values.

I know there are methods such as Collections.min which I could run on the HashMap but I need more than just the lowest value and I need to know the key it corresponds to as well. Research has also led me to come across Selection Algorithms but I am confused and not quite sure how to use these. I apologise if a question of this sort has been asked before, I searched for a long time and could not find anything. Thanks pre-emptively for your help.

Quick-select requires an array though, not a hash map – Sleiman Jneidi May 18 '16 at 01:15 — Sleiman Jneidi, May 18 '16 at 01:15

score 3 · Answer 1 · answered May 18 '16 at 01:27

3

List<Entry<Key, Double>> lowestThreeEntries = map.entrySet()
        .stream()
        .sorted(Comparator.comparing(Entry::getValue))
        .limit(3)
        .collect(Collectors.toList());

answered May 18 '16 at 01:27

shmosel

49,289
6
73
138

Hi, I tried your solution and it probably would have worked but it required Java SE 8 and I'm currently using 7. Thanks for your help though! – user3084433 May 18 '16 at 15:42

score 0 · Answer 2 · answered May 18 '16 at 01:19

Put all then entries of your map inside an array. Then, implement a Comparator<Map.Entry<Key,Value>> which compares the map entries according to the value they hold.

And finally, sort the entries of the map according to your shiny comparator. (You can use Arrays.sort)

Graham S · Answer 3 · 2016-05-23T03:45:07.437

0

Consider inverting your map and using a 'MultiMap' (effectively a more user friendly implementation of Map<Key, List<Value>>), the Guava TreeMultiMap should do exactly what you're after.

http://google.github.io/guava/releases/19.0/api/docs/com/google/common/collect/TreeMultimap.html

Edit - Added example (using String in place of the custom object for brevity)

    TreeMultimap<Double, String> map = TreeMultimap.<Double, String>create();
    map.put(4.0, "a");
    map.put(5.0, "b");
    map.put(2.0, "c");
    map.put(12.0, "d");
    map.put(10.0, "e");
    map.put(3.0, "f");

    Iterator<String> iterator = map.values().iterator();
    while (iterator.hasNext()) {
        System.out.println(iterator.next());
    }

This will print out the strings in ascending order according to the double value (c, f, a, b, e, d)

edited May 23 '16 at 03:45

answered May 18 '16 at 01:23

Graham S

176
1
12

Mind posting an example? – shmosel May 18 '16 at 01:32
Afraid I haven't got an example to hand but the docs are pretty good - https://github.com/google/guava/wiki/NewCollectionTypesExplained#multimap – Graham S May 19 '16 at 07:25
However I prefer your answer, nice use of the stream api – Graham S May 19 '16 at 07:26
I'm quite familiar with Guava's collections, but I don't see how they would help with this question. – shmosel May 19 '16 at 07:40
OP wants to sort by values, not keys. – shmosel May 23 '16 at 02:29
Yes, thats why the map is inverted from the original question. In my example, I've used String instead of their custom object – Graham S May 23 '16 at 03:44

Java find multiple lowest key/value pairs in a hashmap

3 Answers3