In Java, I need to group the keys of a hash map based on the basis of their values

Question

I need to find the topN keys.

I have an input as a HashMap in the form as (key : value):

Banana : 13  
Apple: 12  
Mango : 32  
Orange : 12  
Grape : 18  
Pear : 12  
Peach : 18

I created a linked HapMap that is sorted based on values:

private static <K extends Comparable, V extends Comparable> Map<K, V> sortByValues(Map<K, V> map) {
    List<Map.Entry<K, V>> entries = new LinkedList<Map.Entry<K, V>>(map.entrySet());

    Collections.sort(entries, new Comparator<Map.Entry<K, V>>() {

        @Override
        public int compare(Map.Entry<K, V> o1, Map.Entry<K, V> o2) {
            return o2.getValue().compareTo(o1.getValue());
        }
    });
    Map<K, V> sortedMap = new LinkedHashMap<K, V>();
    for (Map.Entry<K, V> entry : entries) {
        sortedMap.put(entry.getKey(), entry.getValue());
    }
    return sortedMap;
}

this gave my the output as:

Mango : 32  
Grape : 18  
Peach : 18  
Banana : 13  
Apple: 12  
Orange : 12  
Pear : 12

Now if I want to the Top-4 fruits, how should I approach if I want the output to be:

Mango :32  
Grape, Peach : 18  
Banana :13  
Apple, Orange, Pear: 12

I tried iterating through the sorted hashMap and compared the values of subsequent elements by doing

int sizeOfMap = myValueSortedMap.size();
ArrayList<String> keyArr = new ArrayList<String>();
int cnt=0,keyVal=0;

while(cnt<(sizeOfMap-1)){

    if(myValueSortedMap.values().toArray()[cnt] == myValueSortedMap.values().toArray()[cnt+1]){

        keyArr.add((String) myValueSortedMap.keySet().toArray()[cnt]+ " , " +(String) myValueSortedMap.keySet().toArray()[cnt+1]);
    }
    else{
        keyArr.add((String) myValueSortedMap.keySet().toArray()[cnt]);
        keyVal = (int) myValueSortedMap.values().toArray()[cnt];
    }
    cnt++;
}

but this does not always work.

I am not able to think of a way around this. Could someone please give me a lead?

You can try to reverse your Map. New map keys will be `number` values from the first map and new map values will be a `list` of first map keys having that value — tfosra, Jul 04 '16 at 08:51

score 8 · Answer 1 · answered Jul 04 '16 at 09:13

You can use a two-step stream process - the first step groups the entries by the numeric value, the second sorts the stream contents, applies the limit of 4 and prints the result.

map.entrySet()
   .stream()
   .collect(Collectors.groupingBy(Map.Entry::getValue))
   // the map now contains integers mapped to a list of map entries
   .entrySet()
   .stream()
   // sort the stream by descending numeric value
   .sorted((o1, o2) -> o2.getKey().compareTo(o1.getKey()))
   // use the first four elements of the stream
   .limit(4)
   .forEach(entry -> System.out.println(entry.getKey() + " " + entry.getValue().stream().map(Map.Entry::getKey).collect(Collectors.joining(", "))));

This results in

32 Mango
18 Grape, Peach
13 Banana
12 Apple, Pear, Orange

tfosra · Answer 2 · 2016-07-04T09:21:02.443

As I said in my comment, you will need to reverse your map first : so Map<String, Integer> will become Map<Integer, List<String>>.

Then, you can retrieve 4 max keys from your new map (formerly the values of your first map) and print their values

Map reverse method

public static <K extends Comparable, V extends Comparable> Map<V, List<K>> reverseMap(Map<K, V> map) {
    Map<V, List<K>> result = new HashMap<>();
    map.entrySet().stream().forEach((entry) -> {
        List<K> lst = result.get(entry.getValue());
        if (lst == null) {
            lst = new ArrayList<>();
            result.put(entry.getValue(), lst);
        }
        lst.add(entry.getKey());
    });
    return result;
}

How to use it

Map<String, Integer> map = new HashMap<>();
map.put("Banana", 13);
map.put("Apple", 12);
map.put("Mango", 32);
map.put("Orange", 12);
map.put("Grape", 18);
map.put("Pear", 12);
map.put("Peach", 18); 

Map<Integer, List<String>> flip = reverseMap(map);

flip.entrySet().stream()
            .sorted(Map.Entry.<Integer, List<String>>comparingByKey().reversed())
            .limit(4)
            .forEach(e -> System.out.println(String.join(", ", e.getValue()) + " : " + e.getKey()));

Here is the result

Mango : 32
Grape, Peach : 18
Banana : 13
Apple, Pear, Orange : 12

score 1 · Answer 3 · edited Jul 04 '16 at 10:36

Just iterate the HashMap and keep the first k elements.

private HashMap<String, Integer> select_k_element(HashMap sortedMap,int k){
    HashMap<String, Integer> res=new HashMap();
    int i=0;
    for (Map.Entry<String, Integer> e : sortedMap.entrySet()) {
        String key=e.getKey();
        int value=e.getValue();
        res.put(key,value);
        i++;
        if(i>=k)
            break;
    }
    return res;
}

Bilesh Ganguly · Answer 4 · 2016-07-04T12:37:49.267

You have to use a Map with the key-value pair (datatypes) reversed. Following is a basic implementation:

private static Map<String, Integer> fruits = new HashMap<>();

static {
    fruits.put("Banana",13);  
    fruits.put("Apple", 12);
    fruits.put("Mango",32);
    fruits.put("Orange",12); 
    fruits.put("Grape",18);
    fruits.put("Pear",12);
    fruits.put("Peach",18); 
}

public static void main(String[] args) {
    TreeMap<Integer, String> freq = new TreeMap<>();

    // Populate the new Map
    fruits.entrySet().forEach(e -> {
        Integer key = e.getValue();
        if(freq.containsKey(key)) { // Update entry if key is already present
            String curVal = freq.get(key);
            String newVal = e.getKey();

            freq.put(key, curVal + ", " + newVal);
        } else { // Add an entry if key is not present
            freq.put(key, e.getKey());
        }
    });

    // Print the new Map
    freq.descendingMap().entrySet().forEach(e -> {
        System.out.println(e.getValue() + " : " + e.getKey());
    });
}

Used TreeMap to keep it sorted as per key and used descendingMap() to print it in descending order.

Output:

Mango : 32
Grape,Peach : 18
Banana : 13
Apple,Pear,Orange : 12

score 1 · Answer 5 · answered Jul 04 '16 at 09:13

1

You can use SortedMap with a "Fruit" Object implementing Compareable.

The map is ordered according to the natural ordering of its keys, or by a Comparator typically provided at sorted map creation time. This order is reflected when iterating over the sorted map's collection views (returned by the entrySet, keySet and values methods). Several additional operations are provided to take advantage of the ordering. (This interface is the map analogue of SortedSet.)

answered Jul 04 '16 at 09:13

hiaclibe

636
9
25

`SortedMap map = new TreeMap<>();` - or see in javadoc the implementing classes of SortedMap. And iterate over the entrySet. – Joop Eggen Jul 04 '16 at 09:17

In Java, I need to group the keys of a hash map based on the basis of their values

5 Answers5

Map reverse method

How to use it

Here is the result