How to return key associated to highest value in nested map (Java)?

Question

I am trying to build a simple program that in essence will return the key associated to the highest value in a nested Map. For example (below numbers are just an example, they are not real).

public class MultiValueMap {

    public static void main(String[] args) {

        Map<String, HashMap<String, Integer>> singers = new HashMap<>();
        singers.put("Elvis", new HashMap<>());
        singers.get("Elvis").put("All Shook up", 8);
        singers.get("Elvis").put("Don't be Cruel", 5);
        singers.get("Elvis").put("Viva las Vegas", 3);

    }

}

The idea here is to get either the top song or lowest rated song. The program should return for example "All Shook Up" if I want the top rated song.

Any ideas on how to accomplish this?

Answer 1

Note that, given you want min and max a HashMap is not the most suitable structure.
You'll need to traverse over all values every time you want an answer to this question. If you use a TreeSet you can reduce that to a simple binary search on all keys.

record SongScore(String songName, int score)  {}

....

Map<String, TreeSet<SongScore>> singers = new HashMap<>();
TreeSet<SongScore> songs = new TreeSet<>(Comparator.comparingInt(SongScore::score));
songs.add(new SongScore("All Shook up", 8));
songs.add(new SongScore("Don't be Cruel", 5));
songs.add(new SongScore("Viva las Vegas", 3));
singers.put("Elvis", songs);

var lowest = singers.values().stream().map(TreeSet::first).min(Comparator.comparingInt(SongScore::score));
var highest = singers.values().stream().map(TreeSet::last).max(Comparator.comparingInt(SongScore::score));

Answer 2

Given

Given your map with

singer_map: interpret -> title_map
title_map: title -> rating

like:

Map<String, HashMap<String, Integer>> singers = new HashMap<>();
singers.put("Elvis", new HashMap<>());
singers.get("Elvis").put("All Shook up", 8);
singers.get("Elvis").put("Don't be Cruel", 5);
singers.get("Elvis").put("Viva las Vegas", 3);

Algorithm

Now define a temporary entry variable for the favoriteTitle. Take the title-map like Map<String, Integer> titles = singers.get("Elvis") and iterate over each entry (e.g. a for-each loop).

In the loop-body of each iteration: If an entry is higher then favoriteTitle or favoriteTitle is empty, then store the current entry.

After the loop you have the favoriteTitle with highest rating for this singer. If the singer has no titles, then there is also no favorite.

What if all or the more than 1 highest rated titles have the same rating?

Sample code

Map<String, Integer> titles = singers.get("Elvis");
Map.Entry<String, Integer> favoriteTitle;

for (Map.Entry<String, Integer> t : titles) {
  System.out.println(t.getKey() + " rated " + t.getValue());
  if (favoriteTitle == null || favoriteTitle.getValue() < t.getValue()) {
    favoriteTitle = t;
  }
}
System.out.println("Favorite: " + favoriteTitle.getKey() + " rated " + favoriteTitle.getValue());

See also:

• GeeksforGeeks: Map.Entry interface in Java with example, tutorial

Answer 3

In Java 8+ use a stream with Comparator like in Finding Key associated with max Value in a Java Map.

Answer 4

Using Java8 streams you can use a pretty simple one liner. This example assumes there is at least one entry in the map with a non-null value.

map.entrySet()  // get all entries
   .stream()   // stream over them
   .max(Comparator.comparingInt(Map.Entry::getValue))  // max over all entries by value (here: rating), comparing them as integers 
   .get().getKey()  // get the entry, then the key (here: title)