0

Possible Duplicate:
How to sort a Map<Key, Value> on the values in Java?

I have a HashMap as following:

 Key Value
  A    5
  B    3
  C    10
  D    4
  E    1
  F    11

I need to find the one with highest value, what do you suggest me to do? should I sort them and get the first one or there is any other faster way?

1
  • Depending on what you want to do, you may also keep track of the largest value in the HashMap yourself as new key value pairs are inserted into the HashMap
    – nhahtdh
    Oct 5, 2012 at 3:47

5 Answers 5

3

I would not advice to do sorting for a search requirement. As adviced by @David Lam, you can perform a search(iteration) as below to find the highest value key.

    Set<String> keys = myMap.keySet();
    Iterator<String> keyIter = keys.iterator();
    String highestValueKey = null;
    while(keyIter.hasNext()){
         String key = keyIter.next();
         if(highestValueKey == null){
             highestValueKey = key;
         }else if(myMap.get(key).intValue() > myMap.get(highestValueKey).intValue()){
             highestValueKey = key;
         }
    }

In the end, highestValueKey will have reference to highest value element's key.

2

This is much more easily solved by using a SortedMap and passing in a Comparator for the values:

final Map<String, Integer> map = new HashMap<String, Integer>();
map.put("A", 5);
map.put("B", 3);
map.put("C", 10);
map.put("D", 4);
map.put("E", 1);
map.put("F", 11);
map.put("G", 11);
map.put("H", 10);

TreeMap<String, Integer> sorted = new TreeMap<String, Integer>(new Comparator<String>() {
  // Note: this comparator imposes orderings that are inconsistent with equals.
  @Override
  public int compare(String a, String b) {
    if (map.get(a) >= map.get(b)) {
      return -1;
    } else {
      return 1;
    } // returning 0 would merge keys
  }
});
sorted.putAll(map);


Entry<String, Integer> first = sorted.firstEntry();
System.out.println("Highest value: " + first.getValue() + is for key: " + first.getKey());

// If duplicate keys are never a concern, you can stop here.  Otherwise, one may 
// continue below to find all keys that may be mapped to an equal highest value:
List<String> others = new LinkedList<String>();
for (Entry<String, Integer> entries : sorted.entrySet()) {
  if (entries.getValue().equals(first.getValue())) {
    others.add(entries.getKey());
  } else {
    break;
  }
}

System.out.println("All keys mapped to this highest value: " + others);

Prints out:

Highest value: 11 is for key: G
All keys mapped to this highest value: [G, F]
10
  • I have a bit of doubt whether the TreeMap can still be used as a Map after this.
    – nhahtdh
    Oct 5, 2012 at 4:47
  • I haven't tested, but I just have a bit of trouble imagining how get() and containsKey() will work.
    – nhahtdh
    Oct 5, 2012 at 4:53
  • @nhahtdh The logic is sound. Also see stackoverflow.com/a/1283722/24396
    – Steve Kuo
    Oct 5, 2012 at 4:54
  • This solution breaks the contract written in the Map interface, and is fragile. Read the comments in the link for more information. -1
    – nhahtdh
    Oct 5, 2012 at 8:42
  • @nhahtdh I updated to prevent the overwriting of keys with the same values. This example should resolve what the poster is looking for "the one with the highest value". Agree that better solutions exist, but for this scenario, without adopting any third party libraries (Guava), this should suffice.
    – Cuga
    Oct 5, 2012 at 12:24
1

just iterate through the keys and keep track of the highest one O(n)

0

If you need to do the "find the largest value" operation frequently, I suggest you use TreeMap.

Else if you are inserting values into the HashMap and have complete control over it, then keep track of the largest value as you insert values into the HashMap.

EDIT: You will need to use HashMap either way as shown here

1
  • TreeMap doesn't work here, since it order based on key, while OP wants to find the value.
    – nhahtdh
    Oct 5, 2012 at 3:54
-2

Or you can use Bubble Sort to find the highest value

Not the answer you're looking for? Browse other questions tagged or ask your own question.