Get the keys with the biggest values from a hashmap?

java hashmap

36,309

Solution 1

If you have to use a HashMap, then the simplest way is probabably just to loop through the Map looking for the maximum

Entry<String,Integer> maxEntry = null;

for(Entry<String,Integer> entry : uniqueNames.entrySet()) {
    if (maxEntry == null || entry.getValue() > maxEntry.getValue()) {
        maxEntry = entry;
    }
}
// maxEntry should now contain the maximum,

Solution 2

Most obvious, now allowing for multiple with largest occurrence value:

Integer largestVal = null;
List<Entry<String, Integer>> largestList = new ArrayList<Entry<String, Integer>>();
for (Entry<String, Integer> i : uniqueNames.entrySet()){
     if (largestVal == null || largestVal  < i.getValue()){
         largestVal = i.getValue();
         largestList .clear();
         largestList .add(i);
     }else if (largestVal == i.getValue()){
         largestList .add(i);
     }
}

Another option would be to use Guava's BiMap.

BiMap<String, Integer> uniqueNames = ...;
List<Integer> values = Lists.newArrayList(uniqueNames.values());
Collections.sort(values);
String name = uniqueNames.inverse().get(values.get(0));

Solution 3

There are two ways of going about this actually.

If you are going to be doing this frequently, I would actually suggest storing the mapping in reverse, where the key is the number of times a name has appeared, and the value is a list of names which appeared that many times. I would also use a HashMap to perform the lookups in the other direction as well.

TreeMap <Integer, ArrayList <String>> sortedOccurrenceMap =
               new TreeMap <Integer, ArrayList <String>> ();
HashMap <String, Integer> lastNames = new HashMap <String, Integer> ();
boolean insertIntoMap(String key) {
    if (lastNames.containsKey(key)) {
        int count = lastNames.get(key);
        lastNames.put(key, count + 1);

        //definitely in the other map
        ArrayList <String> names = sortedOccurrenceMap.get(count);
        names.remove(key);
        if(!sortedOccurrenceMap.contains(count+1))
            sortedOccurrenceMap.put(count+1, new ArrayList<String>());
        sortedOccurrenceMap.get(count+1).add(key);
    }
    else {
        lastNames.put(key, 1);
        if(!sortedOccurrenceMap.contains(1))
            sortedOccurrenceMap.put(1, new ArrayList<String>());
        sortedOccurrenceMap.get(1).add(key);
    }
}

Something similar for deleting...

And finally, for your search:

ArrayList <String> maxOccurrences() {
    return sortedOccurrenceMap.pollLastEntry().getValue();
}

Returns the List of names that have the max occurrences.

If you do it this way, the searching can be done in O(log n) but the space requirements increase (only by a constant factor though).

If space is an issue, or performance isn't a problem, simply iterate through the uniqueNames.keySet and keep track of the max.

36,309

Author by

steven

Updated on July 05, 2022

Comments

steven about 2 years
I have a HashMap defined like this...
```
HashMap<String,Integer> uniqueNames = new HashMap<String,Integer>();
```
It stores a name, and the occurence of that name. For example...
```
uniqueNames.put("lastname",42);
```
How can I get the name with the highest occurrence?

For some more information, I'm working with a binary search tree of "people", storing the unique names and frequencies in a HashMap. What I want to do is to print the most common last names, and someone told me to use HashMap as I wanted to store a String together with an Integer. Maybe I should use a class to store the name and frequency instead? Could someone please offer some suggestions.
steven almost 13 years

Using your first method, how could I then, having the number of the most common lastname, find the lastnames that occurs that many times? I'll look into the other method, thanks.
John B almost 13 years

The point is that you have the Entry which contains both the name and count with the highest count.
steven almost 13 years

What if there are more than one lastname occuring X times, when X is the biggest frequency?
steven almost 13 years

What if there's more than one such entry? Save them in an array?
John B almost 13 years

How do you mean? If there are multiple names with the same occurrence count?
Kaushik Shankar almost 13 years

I updated the response with code and I think you will understand. Not too much space is taken, since almost all things are pointers anyway.