I want to find the keys associated with the maximum value in a HashMap<Integer,Integer>.
I have seen the question Finding Key associated with max Value in a Java Map, but there are certain restrictions while using HashMap.
Any help would be appreciated.
What you can do here is just sort your HashMap and pick the first or last keys to get max or min values.
public LinkedHashMap<Integer,Integer> sortHashMapByValues(HashMap<Integer,Integer> passedMap) {
List<Integer> mapKeys = new ArrayList<Integer>(passedMap.keySet());
List<Integer> mapValues = new ArrayList<Integer>(passedMap.values());
Collections.sort(mapValues);
Collections.sort(mapKeys);
LinkedHashMap<Integer,Integer> sortedMap =
new LinkedHashMap<Integer,Integer>();
Iterator valueIt = mapValues.iterator();
while (valueIt.hasNext()) {
Object val = valueIt.next();
Iterator keyIt = mapKeys.iterator();
while (keyIt.hasNext()) {
int key = (Integer)keyIt.next();
int comp1 = (Integer)passedMap.get(key);
int comp2 = (Integer)val;
if (comp1 == comp2){
passedMap.remove(key);
mapKeys.remove(key);
sortedMap.put(key,(Integer) val);
break;
}
}
}
return sortedMap;
}
Remember -Their may be more then one keys with same value.
So long as you commit to the map being of type HashMap, you will not do better than iterating over all the key/value pairs in the map, looking for the maximum value. Such a hash table is organized internally for maximum speed in finding keys by their hash code; the organization is indifferent to the values associated with those keys.
To best solve your problem, you need an inverted index on the values. Since several keys can bear the same value in your original map (assuming it was not a bijection), the inverted index is really a multimap, where any given integral key (taken from the set of those that were your original map values) can be associated with any number of integral values (which were your original map keys).
If your inverted index is of type NavigableMap, with the value type being a collection of integers, then you can use the NavigableMap#lastEntry() method to find the pairing of the greatest integral key and its corresponding value. Alternately, if you merely had a SortedMap in hand, you could still use its SortedMap#lastKey() method to find the key in question. This assumes that the map is ordered by the natural ordering of integers, from lowest to highest.
The Guava library provides a set of multimap types, of which the TreeMultimap type exposes a view of type SortedMap with its TreeMultimap#asMap() method. I recommend you try using that one first.
If you only need to find this answer once for a given input map, and don't want to bother building the entire inverted index, try the following O(n) solution:
public static <T extends Number & Comparable<? super T>>
Collection<? extends T> keysForMaxValueIn(Map<? extends T, ? extends T> map) {
final int size = map.size();
switch (size) {
case 0:
return Collections.emptySet();
case 1:
return Collections.singleton(map.keySet().iterator().next());
default:
final T max = Collections.max(map.values());
// We know that there will be no duplicates in the original key set.
final Collection<T> keys = new ArrayList<T>(size);
for (Map.Entry<? extends T, ? extends T> entry : map.entrySet())
if (max.equals(entry.getValue()))
keys.add(entry.getKey());
return keys;
}
}
Since HashMap has no ordering, the simplest solution is probably best. If you want only one key, then it's just
Comparator<Map.Entry<Integer, Integer>> comparator =
new Comparator<Map.Entry<Integer, Integer>>() {
public int compare(
Map.Entry<Integer, Integer> e1, Map.Entry<Integer, Integer> e2) {
return e1.getValue().compareTo(e2.getValue());
}
};
return Collections.max(map.entrySet(), comparator).getKey();
If you want all the keys associated with the maximum value, it's a bit trickier; you'd probably do something like
Integer bestSeenValue = null;
List<Integer> bestKeys = new ArrayList<>();
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
if (bestSeenValue == null || entry.getValue() > bestSeenValue) {
bestSeenValue = entry.getValue();
bestKeys.clear();
}
if (entry.getValue().equals(bestSeenValue)) {
bestKeys.add(entry.getKey());
}
}
This code will print all the keys with maximum value
public class NewClass4 {
public static void main(String[] args)
{
HashMap<Integer,Integer>map=new HashMap<Integer, Integer>();
map.put(1, 50);
map.put(2, 60);
map.put(3, 30);
map.put(4, 60);
map.put(5, 60);
int maxValueInMap=(Collections.max(map.values())); // This will return max value in the Hashmap
for (Entry<Integer, Integer> entry : map.entrySet()) { // Itrate through hashmap
if (entry.getValue()==maxValueInMap) {
System.out.println(entry.getKey()); // Print the key with max value
}
}
}
}
