java exception: Comparison method violates its general contract

Question

I have already checked previous posts on this topic -- this and this. In spite of that, I couldn't figure out how the contract violation can happen in my code given below.

public class ScoreComparator 
implements Comparator<Map.Entry<?, Double>> {

public int compare(Map.Entry<?, Double> o1, 
        Map.Entry<?, Double> o2) {
    return o1.getValue().compareTo(o2.getValue());
}   
}

The way I make use of this is as follows:

List<Entry<String, Double>> entryList = 
        new ArrayList<Entry<String, Double>>(
                iterTypeScoreMap.get(keyToSort).entrySet());
Collections.sort(entryList, new ScoreComparator());

and iterTypeScoreMap is declared as follows

ConcurrentHashMap<String, Map<String, Double>> iterTypeScoreMap;

The map (iterTypeScoreMap) can change during the sort which is why I made a copy of the list and then call sort on it.

Since I am using the built-in compareTo method of Double, shouldn't that take care of the contracts? Another thing that makes this hard to debug is that this exception doesn't happen always; only happens during some of the runs. What could be the bug here?

Thanks in advance.

Do you use this comparator to directly sort a `SortedMap`? Or you use it on separate collection (eg. `List>`? — Jack, Jan 15 '15 at 22:34
Are the values in your map potentially changing during the sort? — Sbodd, Jan 15 '15 at 22:49
Other related questions: ["Comparison method violates its general contract!"](http://stackoverflow.com/questions/8327514/comparison-method-violates-its-general-contract) as well as [Comparison Method violates its general contract in Java 7](http://stackoverflow.com/questions/9486605/comparison-method-violates-its-general-contract-in-java-7) — gknicker, Jan 15 '15 at 23:36
@Jack, good point. Included that in the edit to the question. — Raghava, Jan 15 '15 at 23:38

score 3 · Accepted Answer · answered Jan 15 '15 at 23:40

3

What's happening is that your sort order is changing during the sort operation, due to the entry values (scores) being changed concurrently.

It doesn't help to make a copy of the map's entrySet() when the entries themselves are being concurrently modified. You'd have to deep copy the collection, in other words copy all of the Entry objects as well, in order to prevent the error. As it stands, the list you're sorting has references to the same Entry objects as the original map.

answered Jan 15 '15 at 23:40

gknicker

5,509
2
25
41

yes, I think that was the problem. Thank you. I created AbstractMap.SimpleImmutableEntry based on the map entries and inserted them into the list to be sorted. That seems to have fixed it. – Raghava Jan 16 '15 at 01:12

score 0 · Answer 2 · answered Jan 15 '15 at 22:32

0

I think the issue is that a.compareTo(b)==0 should imply a.equals(b).

However, if your keys are different but values are the same, then the two would have a.compareTo(b)==0 but a.equals(b) would be false.

answered Jan 15 '15 at 22:32

k_g

4,333
2
25
40

No, this is not implied. Just strongly suggested. – Jack Jan 15 '15 at 22:33
I think that whatever sorting algorithm the OP is using might assume (although incorrectly) that it is implied. I know `TreeSet` does, removing elements that are not equal but where `a.compare(b)==0`. – k_g Jan 15 '15 at 22:37
From `TreeMap` documentation: _The behavior of a sorted map is well-defined even if its ordering is inconsistent with equals; it just fails to obey the general contract of the Map interface._ – Jack Jan 15 '15 at 22:43

java exception: Comparison method violates its general contract

2 Answers2