When sorting a map based on a value, some values ​​are missing. What causes this strange behavior?

Question

I am trying to sort a map based on word frequency (i.e. based on meaning). For this, I have an overridden comparator and passed to TreeMap , but I get this strange output.

 public class WordFrequency { public static String sentence = "one three two two three three four four four"; public static Map<String, Integer> map; public static void main(String[] args) { map = new HashMap<>(); String[] words = sentence.split("\\s"); for (String word : words) { Integer count = map.get(word); if (count == null) { count = 1; } else { ++count; } map.put(word, count); } Comparator<String> myComparator = new Comparator<String>() { @Override public int compare(String s1, String s2) { if (map.get(s1) < map.get(s2)) { return -1; } else if (map.get(s1) > map.get(s2)) { return 1; } else { return 0; } } }; SortedMap<String, Integer> sortedMap = new TreeMap<String, Integer>(myComparator); System.out.println("Before sorting: " + map); sortedMap.putAll(map); System.out.println("After Sorting based on value:" + sortedMap); } } 

Output:

 Before sorting: {two=2, one=1, three=3, four=3} After sorting based on value:{one=1, two=2, three=3} 

Expected Result:

 {one=1, two=2, four=3,three=3} 

Answer 1

Your compare method does not fulfill the contract of the Map interface, since it compares values ​​instead of keys. Your implementation forces two keys with the same value to be considered the same key. Therefore, your sortedMap does not contain the four key, which has the same meaning as the three key.

Note that the ordering supported by the tree map , like any sorted map, and whether an explicit comparator provides, must match if this sorted map correctly implements the map interface . (See “Comparison” or “Comparator” for an exact match with peers.) This is because the map interface is determined using the equality operation, but the sorted map performs all key mappings using the compareTo (or comparison) method , so there are two keys that are considered equal to this method are equal in terms of the sorted map . The behavior of a sorted card is well defined, even if its order is not consistent with the equalities; he simply does not comply with the general contract of the map interface.

TreeMap link

You can fix this problem by comparing the keys when the values ​​are equal:

  Comparator<String> myComparator = new Comparator<String>() { @Override public int compare(String s1, String s2) { if (map.get(s1) < map.get(s2)) { return -1; } else if (map.get(s1) > map.get(s2)) { return 1; } else { return s1.compareTo(s2); } } }; 

This will give you the result:

 After sorting based on value:{one=1, two=2, four=3, three=3} 

Since four<three based on the natural ordering of strings.

Answer 2

Because of your compare() only Map values ​​are counted. Then three=3, four=3 has the same value 3 . They are then considered as duplicates when they are added to the TreeMap .

Answer 3

This is because your implementation tells TreeMap that the map [three] and map [four] are essentially the same element, because they are “equal” to each other according to your comparator.

Change "return 0" in Comparator to "return s1.compareTo (s2)" and you will have

 Before sorting: {two=2, one=1, three=3, four=3} After Sorting based on value:{one=1, two=2, four=3, three=3} 

(I believe that you can understand why the "four" precede the "three" in this case)