need a method to find a value in HashMap

Question

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?

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 05 '12 at 03:47

score 3 · Answer 1 · answered Oct 05 '12 at 03:59

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.

Cuga · Accepted Answer · 2012-10-05T12:43:24.990

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]

edited Oct 05 '12 at 12:43

answered Oct 05 '12 at 04:02

Cuga

17,668
31
111
166

I have a bit of doubt whether the TreeMap can still be used as a Map after this. – nhahtdh Oct 05 '12 at 04:47
I haven't tested, but I just have a bit of trouble imagining how get() and containsKey() will work. – nhahtdh Oct 05 '12 at 04:53
@nhahtdh The logic is sound. Also see http://stackoverflow.com/a/1283722/24396 – Steve Kuo Oct 05 '12 at 04: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 05 '12 at 08: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 05 '12 at 12:24
@Cuga: The code is at best patchy (and most of the functions in TreeMap is broken). If you have already coded this far, writing a reverse map from Integer -> List might be better. – nhahtdh Oct 05 '12 at 14:52
It's not really patchy. The `Comparator` is an anonymous class, used only in one location and for one specific purpose, so the `equals` contract with `compareTo` doesn't really come into play in this closed-example. It completely solves the OP's quest which is just to find the one key. After gotten, she can continue to use the original `HashMap` as she desires. Only use the `TreeMap` for this one task-- finding the key with the max value in its own function, and then she'll always be fine. – Cuga Oct 05 '12 at 14:59
@nhahtdh To be clear, I'm not saying he should ditch the `HashMap` and use a `TreeMap` from here on out-- merely to only use it for the purpose of finding the sought-answer, ideally in its own, focused function designed to do exactly this which will return the result. – Cuga Oct 05 '12 at 15:01
@Cuga: Your method is no better than looping through all the values and get the maximum value. The TreeMap is totally unnecessary and has a bad example of implementing Comparator for TreeMap. – nhahtdh Oct 05 '12 at 15:07
That's not at all true. Simply looping thru and keeping a record of the max value will still need special care for recording duplicate keys. In any event, it's an entirely acceptable solution to completely address the problem. – Cuga Oct 05 '12 at 15:15

score 1 · Answer 3 · answered Oct 05 '12 at 03:48

1

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

answered Oct 05 '12 at 03:48

David Lam

4,689
3
23
34

score 0 · Answer 4 · edited May 23 '17 at 11:56

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

edited May 23 '17 at 11:56

Community

1
1

answered Oct 05 '12 at 03:51

John Eipe

10,922
24
72
114

TreeMap doesn't work here, since it order based on key, while OP wants to find the value. – nhahtdh Oct 05 '12 at 03:54

score -2 · Answer 5 · answered Oct 05 '12 at 03:55

-2

Or you can use Bubble Sort to find the highest value

answered Oct 05 '12 at 03:55

Đức Bùi

517
1
6
22

need a method to find a value in HashMap

5 Answers5