sorting - Java Map sort by value

Question

I was looking for ways of sorting Map<String, Integer> by values. I found this post, which solved my sorting problem, but not exactly. According to the post, I wrote the following code:

import java.util.*;

public class Sort {

    static class ValueComparator implements Comparator<String> {

        Map<String, Integer> base;

        ValueComparator(Map<String, Integer> base) {
            this.base = base;
        }

        @Override
        public int compare(String a, String b) {
            if (base.get(a) >= base.get(b)) {
                return 1;
            } else {
                return -1;
            }
        }
    }

    public static void main(String[] args) {
        HashMap<String, Integer> map = new HashMap<String, Integer>();
        ValueComparator vc = new ValueComparator(map);
        TreeMap<String, Integer> sorted = new TreeMap<String, Integer>(vc);
        map.put("A", 1);
        map.put("B", 2);
        sorted.putAll(map);
        for (String key : sorted.keySet()) {
            System.out.println(key + " : " + sorted.get(key)); // why null values here?
        }
        System.out.println(sorted.values()); // But we do have non-null values here!
    }
}

Output:

A : null
B : null
[1, 2]
BUILD SUCCESSFUL (total time: 0 seconds)

As you can see from the output, the get method always returns null. The reason is my ValueComparator.compare() method never returns 0, which I've figured out by making this post.

Someone suggested in that post the following to solve the null value problem:

        public int compare(String a, String b) {
            if (base.get(a) > base.get(b)) {
                return 1;
            }else if(base.get(a) ==  base.get(b)){
                return 0;
            }
            return -1;  
        }

I've tested this piece of code and it introduces a key merging problem. In other words, when the values are equal their corresponding keys are merged.

I've also tried the following:

            public int compare(String a, String b) {
                if (a.equals(b)) return 0;
                if (base.get(a) >= base.get(b)) {
                    return 1;
                } else return -1;
            }

It does not work either. Some of the values are still null. Besides, this workaround might potentially have logical problems.

Anyone can propose a fully working solution to my problem? I'd like the sort by value function to work and the get method to work at the same time.

Answer 1

In your compare function, when the values are equal, you should then compare the keys. This will ensure that different keys having the same value will not be "merged", because it disambiguates entries that would otherwise compare equal.

For example:

    @Override
    public int compare(String a, String b) {
        Integer x = base.get(a);
        Integer y = base.get(b);
        if (x.equals(y)) {
            return a.compareTo(b);
        }
        return x.compareTo(y);
    }

(you'll need to modify the code above to match your policy for null values)

Note that your approach of sorting on values is pretty fragile, though. Your "sorted" map will not support addition of new entries, which could be pretty confusing.