Sorting HashMap by value using a TreeMap and Comparator

Question

Im using the following code to create a hashmap and then sort the values in the hashmap by using a treemap and a comparator. However, the output is rather unexpected. So any thoughts as to what Im doing wrong would be helpful

Code

public static void main(String[] args) {
    System.out.println("Most freq"+mostFreq(" i me hello hello hello me"));
}


public static String[] mostFreq(String str){

    if ((str==null)||( str.trim().equalsIgnoreCase("")))
        return null;

    String[] arr = new String[10];

    String[] words= str.split(" ");

    Map <String,Integer> map = new HashMap<String,Integer>();

    for (String word :words)
    { 
        int count =0;
        if (map.containsKey(word))
        {     
            count= map.get(word);
            map.put(word, count+1);
        }             
        else
            map.put(word, 1);
    }

    MyComparator comp= new MyComparator(map);
    Map<String,Integer> newMap= new TreeMap(comp);
    newMap.putAll(map);
    Iterator it= newMap.entrySet().iterator();
    while (it.hasNext())
    {
        Map.Entry pairs = (Map.Entry) it.next();
        System.out.println("Key  "+pairs.getKey()+"-- value"+pairs.getValue());
    }

    return arr;
}

Here's the comparator

package samplecodes;

import java.util.Comparator;
import java.util.Map;

public class MyComparator implements Comparator {

    Map map;

    public MyComparator(Map map){
        this.map=map;
    }

    @Override
    public int compare(Object o1, Object o2) {
        return ((Integer)map.get(o1) >(Integer)map.get(o2)? (Integer)map.get(o1):(Integer)map.get(o2));
    }

}

And the output is of the form

me-2
hello-3
i-3

Answer 1

What you are doing is really a misuse of tools.

I believe what you need to do is:

1. Have a list/array of input words (still fine that you get it by splitting the input string)
2. Create a Map to store the word as key, and frequency as value
3. Have a collection of unique words, then sort the collection base on the the frequency
4. When you are doing the output, traverse the sorted unique word list, for each element, get the frequency from the frequencyMap, and output the word + frequency.

Of course you can still make use of something like a TreeSet and use frequency as key, but you should have list of words as the value of this map (aka Multi-Map), instead of writing a problematic comparator which do not follow the contract of Comparator: http://docs.oracle.com/javase/6/docs/api/java/util/Comparator.html#compare%28T,%20T%29 Both your original implementation and the one in comment of one of the answers does not comply with the rule of sgn(compare(x, y)) == -sgn(compare(y, x)) for all x and y (The original one is even worse).

some code snippet just for giving you hints:

List<String> words = ....;
Map<String, Integer> wordFrequencyMap = new HashMap<String, Integer>();
// iterate words and update wordFrequencyMap accordingly
List<String> uniqueWords = new ArrayList<String>(new HashSet<String>(words));
Collections.sort(uniqueWords, new WordFrequencyComparator<String>(wordFrequencyMap));
for (String w : uniqueWords) {
  System.out.println("word : " + w + "  frequency : " + wordFrequencyMap.get(w));
}

The missing part shouldn't be anything difficult.

Answer 2

The Java Doc of TreeMap clearly states that:

A Red-Black tree based NavigableMap implementation. The map is sorted according to the natural ordering of its keys

we should not violate this rule by using TreeMap to sort by values.

However to sort by values, we can do the following:

1. Create a LinkedList of entries of the map
2. using Collection.sort to sort the entries
3. Inserting the sorted entries to a LinkedHashMap: keeps the keys in the order they are inserted, which is currently sorted on natural ordering.

4. Return the LinkedHashMap as the sorted map.

    public 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(Entry<K, V> o1, Entry<K, V> o2) {
               return o1.getValue().compareTo(o2.getValue());
           }
       });
   
   
       Map<K,V> sortedMap = new LinkedHashMap<K,V>();
   
       for(Map.Entry<K,V> entry: entries){
           sortedMap.put(entry.getKey(), entry.getValue());
       }
   
       return sortedMap;
   }
   
   }
   

Reference: Sorting Map by value

Answer 3

Please check the JavaDoc of compare: You do not return the bigger value, but -1 for o1 < o2, 0 for o1 = o2 and 1 for o1 > o2. So you could write:

@Override
public int compare(Object o1, Object o2) {
    return ((Integer) map.get(o1)).compareTo((Integer) map.get(o2);
}