Get minvalue of a Map(Key,Double)

Question

Hi all, is there a method (maybe with Google Collections) to obtain the min value of a Map(Key, Double)

In traditional way, I would have to sort the map according to the values, and take the first/last one. thanks

Answer 1

You can use the standard Collections#min() for this.

Map<String, Double> map = new HashMap<String, Double>();
map.put("1.1", 1.1);
map.put("0.1", 0.1);
map.put("2.1", 2.1);

Double min = Collections.min(map.values());
System.out.println(min); // 0.1

Update: since you need the key as well, well, I don't see ways in Collections or Google Collections2 API since a Map is not a Collection. The Maps#filterEntries() is also not really useful, since you only know the actual result at end of iteration.

Most straightforward solution would then be this:

Entry<String, Double> min = null;
for (Entry<String, Double> entry : map.entrySet()) {
    if (min == null || min.getValue() > entry.getValue()) {
        min = entry;
    }
}

System.out.println(min.getKey()); // 0.1

(nullcheck on min left aside)

Answer 2

In traditional way, I would have to sort the map according to the values, and take the first/last one. thanks

No, you wouldn't. You would have to iterate through all values and at each step compare the current element with the smallest one seen so far. That's O(n), compared with O(n*log(n)) for sorting - a potentially huge difference.

BTW, this is exactly how Collections.min() works.

Answer 3

In order to do it efficiently, you may want to define your own data structure, such that it implements the Map interface,but also allows efficient getMin() operation.

This can be done using two internal data structures: a map and a tree (or heap data structure). Each time a new pair (K,V) is added, add them to the map, and also to the tree (as a single entry). This allows O(1) time for get(Key) operations, and O(log n) time for addition, removal, and getMin operations.

Answer 4

I'd be inclined to use a Google Collections BiMap:

     String minKey = HashBiMap.create(map).inverse().get(Collections.min(map.values()));

Or something like that (not tested).

Answer 5

You still can use Collections.min with a custom Comparator to get the Map.Entry with the lower value:

Map<String, Double> map = new HashMap<String, Double>();
map.put("1.1", 1.1);
map.put("0.1", 0.1);
map.put("2.1", 2.1);
Entry<String, Double> min = Collections.min(map.entrySet(), new Comparator<Entry<String, Double>>() {
    public int compare(Entry<String, Double> entry1, Entry<String, Double> entry2) {
        return entry1.getValue().compareTo(entry2.getValue());
    }
});
System.out.printf("%s: %f", min.getKey(), min.getValue()); // 0.1: 0.100000