CODEWITHSUNDEEP
javacomparator
James Raitsev
James Raitsev

Reputation: 96421

Sorting Map by Value, clarification needed

This has been asked several times, i know, but help me understand something.

You have a map you need sorted by Value

    Map<String, Integer> m = new HashMap<String, Integer>();
    m.put("a", 1);
    m.put("b", 13);
    m.put("c", 22);
    m.put("d", 2);

You call a method to make it happen

public static List<String> sortByValue(final Map<String, Integer> unsortedMap) {

    List<String> sortedKeys = new ArrayList<String>();
    sortedKeys.addAll(unsortedMap.keySet());

    Collections.sort(sortedKeys, new MapComparator(unsortedMap));

    return sortedKeys;
}

You have a comparator class

public MapComparator(Map<String, Integer> m) {
    this.m = m;
}

@Override
public int compare(String a, String b) {

    int x = m.get(a);
    int y = m.get(b);

    if (x > y)
        return x;
    if (y > x)
        return y;

    return 0;

}

This code, obviously is flawed. Please help me understand why?

Upvotes: 0

Views: 115

Answers (5)

卢声远 Shengyuan Lu
卢声远 Shengyuan Lu

Reputation: 32004

public static List<String> sortByValue(final Map<String, Integer> unsortedMap) {
    List<String> sortedKeys = new ArrayList<String>();
    sortedKeys.addAll(unsortedMap.keySet());

    Collections.sort(sortedKeys, new Comparator<String>(){
        public int compare(String s1, String s2) {
            return unsortedMap.get(s1).compareTo(unsortedMap.get(s2));
        }});
    return sortedKeys;
}

Upvotes: 0

akkyy
akkyy

Reputation: 31

@Override
public int compare(String a, String b) {

    Integer x = m.get(a);
    Integer y = m.get(b);

    return x.compareTo(y);
}

Since you have Integer objects as values, you can use the implicit method to compare the objects and return 1, 0 or -1.

Upvotes: 1

seh
seh

Reputation: 15259

Your comparator only ever indicates that the values are equal or that the left is greater than the right.

Consider the case where x is 1 and y is 2. Your comparator will return 2—a positive number—when it should have returned a negative number.

I recommend that you study the Comparator interface documentation again to see which part of the contract you're missing out on here.

Upvotes: 0

Mike Samuel
Mike Samuel

Reputation: 120516

Comparators don't return the greater or lesser value. They return a negative value to indicate less-than or a positive value to indicate greater than.

if (x > y)
    return x;
if (y > x)
    return y;

return 0;

should probably be

if (x > y)
    return -1;
if (y > x)
    return 1;

return 0;

Upvotes: 0

Louis Wasserman
Louis Wasserman

Reputation: 198143

  if (x > y)
    return x;
  if (y > x)
    return y;

  return 0;

You should be returning 1 if x > y and -1 if y > x. The Comparator contract specifies that you return a negative number if the first value is less than the second, a positive number if the first is greater than the second, and zero if they're equal.

(Mind you, as it stands, this Comparator implementation will break in very confusing ways if you ever happen to use values that aren't in the original map.)

Better yet, just return Integer.compare(x, y), which does all that for you. (Only in Java 7, though.)

Upvotes: 2

Related Questions