CODEWITHSUNDEEP
javasortingdictionarycomparatortreemap
Anand
Anand

Reputation: 21320

TreeMap sort is not working on equal values

I have written a method that sorts the TreeMap by its values

public TreeMap<String, Integer> sortByValues(final TreeMap<String, Integer> map) {
        Comparator<String> valueComparator =  new Comparator<String>() {
            public int compare(String k1, String k2) {
                int compare = map.get(k1).compareTo(map.get(k2));
                return compare;
            }
        };
        Map<String, Integer> sortedByValues = new TreeMap<String, Integer>(valueComparator);
        sortedByValues.putAll(map);
        return sortedByValues;
    }

The above method works fine in normal case but fails when there is a duplicate value present in the TreeMap. Any duplicate value entry is removed from the Map.After googling it I found the solution as

public Map<String, Integer> sortByValuesTree(final Map<String, Integer> map) {
        Comparator<String> valueComparator =  new Comparator<String>() {
            public int compare(String k1, String k2) {
                int compare = map.get(k1).compareTo(map.get(k2));
                if (compare == 0) return 1;
                else return compare;
            }
        };
        Map<String, Integer> sortedByValues = new TreeMap<String, Integer>(valueComparator);
        sortedByValues.putAll(map);
        return sortedByValues;
    }

The above works fine but I am not able to understand why first method didn't work. Why did it remove duplicate value entry? Can someone please let me know

Upvotes: 1

Views: 2933

Answers (2)

C. K. Young
C. K. Young

Reputation: 223003

Actually, especially in Java 7 onwards, even your second method is not going to work. (See below for why.) Anyway, the reason is that maps must have distinct keys, and when you are using your value as key, two equal values would be treated as equal keys.

The proper fix, by the way, is to sort by value, then by key:

int compare = map.get(k1).compareTo(map.get(k2));
if (compare == 0) {
    compare = k1.compareTo(k2);
}
return compare;

Proper comparators must follow three rules:

  1. compare(a, a) == 0 for all values of a.
  2. signum(compare(a, b)) == -signum(compare(b, a)) for all values of a and b.
  3. if signum(compare(a, b)) == signum(compare(b, c)), then signum(compare(a, c)) must also have the same value, for all values of a, b, and c.

Upvotes: 3

JB Nizet
JB Nizet

Reputation: 691715

Why did it remove duplicate value entry?

Because that's the very definition of a Map: for a given key, it stores one value. If you put another value for a key that is already in the map, the new value replaces the old one for this key. And since you told the map that a key is equal to another one when their associated value are equal, the map considers two keys to be equal when their value are equal.

Note that your solution is a bad one which probably works by accident. Indeed, your comparator doesn't respect the contract of the Comparator interface. Indeed, when two values are equal, you arbitrarily decide to make the first one bigger than the second one. This means that your comparator makes A > B and B > A true at the same time, which is not correct.

Sorting a TreeMap by value just looks like an absurdity to me. You won't be able to add any new value to the map anyway, since it would require the entry to already exist in the old map. Shouldn't you simply have a sorted list of map entries?

Upvotes: 4

Related Questions