Sorting Java TreeMap by value not working when more than two values have the same sort-property

I want to sort a Java TreeMap based on some attribute of value. To be specific, I want to sort a TreeMap<Integer, Hashset<Integer>> based on the size of Hashset<Integer>. To achieve this, I have done the following:

A Comparator class:

private static class ValueComparer implements Comparator<Integer> {
    private Map<Integer, HashSet<Integer>>  map = null;
    public ValueComparer (Map<Integer, HashSet<Integer>> map){
        super();
        this.map = map;
    }

@Override
    public int compare(Integer o1, Integer o2) {
        HashSet<Integer> h1 = map.get(o1);
        HashSet<Integer> h2 = map.get(o2);

        int compare = h2.size().compareTo(h1.size());

        if (compare == 0 && o1!=o2){
            return -1;
        }
        else {
            return compare;
        }
    }
}

A 开发者_开发知识库usage example:

TreeMap<Integer, HashSet<Integer>> originalMap = new TreeMap<Integer, HashSet<Integer>>();

//load keys and values into map

ValueComparer comp = new ValueComparer(originalMap);
TreeMap<Integer, HashSet<Integer>> sortedMap = new TreeMap<Integer, HashSet<Integer>>(comp);
sortedMap.putAll(originalMap);

The problem:

This doesn't work when originalMap contains more than 2 values of the same size. For other cases, it works alright. When more than two values in the map are of same size, the third value in the new sorted-map is null and throws NullPointerException when I try to access it.

I can't figure out what the problem is. Woule be nice if someone could point out.

Update: Here's an example that works when two values have the same size: http://ideone.com/iFD9c In the above example, if you uncomment lines 52-54, this code will fail- that's what my problem is.

---

Update: You cannot return -1 from ValueComparator just because you want to avoid duplicate keys to not be removed. Check the contract of Comparator.compare.

---

When you pass a Comparator to TreeMap you compute a ("new") place to put the entry. No (computed) key can exist more than once in a TreeMap.

---

If you want to sort the orginalMap by size of the value you can do as follows:

public static void main(String[] args) throws Exception {

    TreeMap<Integer, HashSet<Integer>> originalMap = 
        new TreeMap<Integer, HashSet<Integer>>();

    originalMap.put(0, new HashSet<Integer>() {{ add(6); add(7); }});
    originalMap.put(1, new HashSet<Integer>() {{ add(6); }});
    originalMap.put(2, new HashSet<Integer>() {{ add(9); add(8); }});


    ArrayList<Map.Entry<Integer, HashSet<Integer>>> list = 
        new ArrayList<Map.Entry<Integer, HashSet<Integer>>>();
    list.addAll(originalMap.entrySet());

    Collections.sort(list, new Comparator<Map.Entry<Integer,HashSet<Integer>>>(){
        public int compare(Map.Entry<Integer, HashSet<Integer>> o1,
                           Map.Entry<Integer, HashSet<Integer>> o2) {

            Integer size1 = (Integer) o1.getValue().size();
            Integer size2 = (Integer) o2.getValue().size();
            return size2.compareTo(size1);
        }
    });

    System.out.println(list);
}

---

Your comparator logic (which I'm not sure I follow why you'd return -1 if the set sizes are equal but they keys are different) shouldn't affect what the Map itself returns when you call get(key).

Are you positive you aren't inserting null values into the initial map? What does this code look like?

---

Your comparator doesn't respect the Comparator contract: if compare(o1, o2) < 0, then compare(o2, o1) should be > 0. You must find a deterministic way of comparing your elements when both sizes are the same and the integers are not identical. You could perhaps use the System.identityHashCode() of the integers to compare them in this case.

That said, I really wonder what you could do with such a map: you can't create new Integers and use them to get a value out of the map, and you can't modify the sets that it holds.

Side note: your comparator code sample uses map and data to refer to the same map.

---

You can have TreeMap ordered only by keys. There is no way of creating TreeMap ordered by values, because you will get StackOverflowException.

Think about it. To get an element from a tree, you need to perform comparisions, but to perform comparisions, you need to get elements.

You will have to sort it in other collection or to use Tree, you will have to encapsulate the integer (from entry value) also into the entry key and define comparator using that integer taken from a key.

---

Assuming you cannot use a comparator that returns 0 with a Set, this might work: Add all the elements in originalMap.entrySet() to an ArrayList and then sort the ArrayList using your ValueComparer, changing it to return 0 as necessary.

Then add all the entries in the sorted ArrayList to a LinkedHashMap.

---

I had a similar problem as the original poster. I had a TreeMap i wanted to sort on a value. But when I made a comparator that looked at the value, i had issues because of the breaking of the comparator that JB talked about. I was able to use my custom comparator and still observe the contract. When the valuse I was looking at were equal, i fell back to comparing the keys. I didn't care about the order if values were equal.

    public int compare(String a, String b) {
    if(base.get(a)[0] == base.get(b)[0]){ //need to handle when they are equal
        return a.compareTo(b);
    }else if (base.get(a)[0] < base.get(b)[0]) {
        return -1;
    } else {
        return 1;
    } // returning 0 would merge keys