user1923 user1923 - 28 days ago 4
Java Question

Finding the key whose value is the lowest value in a hashmap

I'm trying to come up with an efficient way to return a key in my

HashMap
that has the lowest value in datastructure. Is there a quick and efficient way to do this besides looping through the entire
HashMap
?

For example, if I have a hashmap that looks like this:

1: 200
3: 400
5: 1


I want to return the key, 5.

Answer

As others have mentioned HashMap itself does not provide this.

So your options are to either compute it on-demand or pre-compute.

To compute it on-demand, you would iterate the HashMap.entrySet()

Depending on the size of the map, frequency of its change and frequency of requiring the key-with-lowest-value, pre-computing (caching) may be more efficient. Something as follows:

class HashMapWithLowestValueCached<K, V extends Comparable> extends HashMap<K, V> {    
    V lowestValue;
    K lowestValueKey;    
    void put(K k, V v) {
      if (v.compareTo(lowestValue) < 0) {
        lowestValue = v; 
        lowestValueKey = k;
      }
      super.put(k, v);
    }
    K lowestValueKey () { return lowestValueKey; }
}
Comments