Java 错误: 比较方法违反了它的一般约定

小开

最佳答案

The exception message is actually pretty descriptive. The contract it mentions is transitivity: if A > B and B > C then for any A, B and C: A > C. I checked it with paper and pencil and your code seems to have few holes:

if (card1.getRarity() < card2.getRarity()) {
return 1;

you do not return -1 if card1.getRarity() > card2.getRarity().

if (card1.getId() == card2.getId()) {
//...
}
return -1;

You return -1 if ids aren't equal. You should return -1 or 1 depending on which id was bigger.

Take a look at this. Apart from being much more readable, I think it should actually work:

if (card1.getSet() > card2.getSet()) {
return 1;
}
if (card1.getSet() < card2.getSet()) {
return -1;
};
if (card1.getRarity() < card2.getRarity()) {
return 1;
}
if (card1.getRarity() > card2.getRarity()) {
return -1;
}
if (card1.getId() > card2.getId()) {
return 1;
}
if (card1.getId() < card2.getId()) {
return -1;
}
return cardType - item.getCardType();  //watch out for overflow!

小开

        if (card1.getRarity() < card2.getRarity()) {
return 1;

However, if card2.getRarity() is less than card1.getRarity() you might not return -1.

You similarly miss other cases. I would do this, you can change around depending on your intent:

public int compareTo(Object o) {
if(this == o){
return 0;
}


CollectionItem item = (CollectionItem) o;


Card card1 = CardCache.getInstance().getCard(cardId);
Card card2 = CardCache.getInstance().getCard(item.getCardId());
int comp=card1.getSet() - card2.getSet();
if (comp!=0){
return comp;
}
comp=card1.getRarity() - card2.getRarity();
if (comp!=0){
return comp;
}
comp=card1.getSet() - card2.getSet();
if (comp!=0){
return comp;
}
comp=card1.getId() - card2.getId();
if (comp!=0){
return comp;
}
comp=card1.getCardType() - card2.getCardType();


return comp;


}
}

小开

Consider the following case:

First, o1.compareTo(o2) is called. card1.getSet() == card2.getSet() happens to be true and so is card1.getRarity() < card2.getRarity(), so you return 1.

Then, o2.compareTo(o1) is called. Again, card1.getSet() == card2.getSet() is true. Then, you skip to the following else, then card1.getId() == card2.getId() happens to be true, and so is cardType > item.getCardType(). You return 1 again.

From that, o1 > o2, and o2 > o1. You broke the contract.

小开

It also has something to do with the version of JDK. If it does well in JDK6, maybe it will have the problem in JDK 7 described by you, because the implementation method in jdk 7 has been changed.

Look at this:

Description: The sorting algorithm used by java.util.Arrays.sort and (indirectly) by java.util.Collections.sort has been replaced. The new sort implementation may throw an IllegalArgumentException if it detects a Comparable that violates the Comparable contract. The previous implementation silently ignored such a situation. If the previous behavior is desired, you can use the new system property, java.util.Arrays.useLegacyMergeSort, to restore previous mergesort behaviour.

I don't know the exact reason. However, if you add the code before you use sort. It will be OK.

System.setProperty("java.util.Arrays.useLegacyMergeSort", "true");

小开

You can use the following class to pinpoint transitivity bugs in your Comparators:

/**
* @author Gili Tzabari
*/
public final class Comparators
{
/**
* Verify that a comparator is transitive.
*
* @param <T>        the type being compared
* @param comparator the comparator to test
* @param elements   the elements to test against
* @throws AssertionError if the comparator is not transitive
*/
public static <T> void verifyTransitivity(Comparator<T> comparator, Collection<T> elements)
{
for (T first: elements)
{
for (T second: elements)
{
int result1 = comparator.compare(first, second);
int result2 = comparator.compare(second, first);
if (result1 != -result2)
{
// Uncomment the following line to step through the failed case
//comparator.compare(first, second);
throw new AssertionError("compare(" + first + ", " + second + ") == " + result1 +
" but swapping the parameters returns " + result2);
}
}
}
for (T first: elements)
{
for (T second: elements)
{
int firstGreaterThanSecond = comparator.compare(first, second);
if (firstGreaterThanSecond <= 0)
continue;
for (T third: elements)
{
int secondGreaterThanThird = comparator.compare(second, third);
if (secondGreaterThanThird <= 0)
continue;
int firstGreaterThanThird = comparator.compare(first, third);
if (firstGreaterThanThird <= 0)
{
// Uncomment the following line to step through the failed case
//comparator.compare(first, third);
throw new AssertionError("compare(" + first + ", " + second + ") > 0, " +
"compare(" + second + ", " + third + ") > 0, but compare(" + first + ", " + third + ") == " +
firstGreaterThanThird);
}
}
}
}
}


/**
* Prevent construction.
*/
private Comparators()
{
}
}

Simply invoke Comparators.verifyTransitivity(myComparator, myCollection) in front of the code that fails.

小开

I had to sort on several criterion (date, and, if same date; other things...). What was working on Eclipse with an older version of Java, did not worked any more on Android : comparison method violates contract ...

After reading on StackOverflow, I wrote a separate function that I called from compare() if the dates are the same. This function calculates the priority, according to the criteria, and returns -1, 0, or 1 to compare(). It seems to work now.

小开

I got the same error with a class like the following StockPickBean. Called from this code:

List<StockPickBean> beansListcatMap.getValue();
beansList.sort(StockPickBean.Comparators.VALUE);


public class StockPickBean implements Comparable<StockPickBean> {
private double value;
public double getValue() { return value; }
public void setValue(double value) { this.value = value; }


@Override
public int compareTo(StockPickBean view) {
return Comparators.VALUE.compare(this,view); //return
Comparators.SYMBOL.compare(this,view);
}


public static class Comparators {
public static Comparator<StockPickBean> VALUE = (val1, val2) ->
(int)
(val1.value - val2.value);
}
}

After getting the same error:

java.lang.IllegalArgumentException: Comparison method violates its general contract!

I changed this line:

public static Comparator<StockPickBean> VALUE = (val1, val2) -> (int)
(val1.value - val2.value);

to:

public static Comparator<StockPickBean> VALUE = (StockPickBean spb1,
StockPickBean spb2) -> Double.compare(spb2.value,spb1.value);

That fixes the error.

小开

I ran into a similar problem where I was trying to sort a n x 2 2D array named contests which is a 2D array of simple integers. This was working for most of the times but threw a runtime error for one input:-

Arrays.sort(contests, (row1, row2) -> {
if (row1[0] < row2[0]) {
return 1;
} else return -1;
});

Error:-

Exception in thread "main" java.lang.IllegalArgumentException: Comparison method violates its general contract!
at java.base/java.util.TimSort.mergeHi(TimSort.java:903)
at java.base/java.util.TimSort.mergeAt(TimSort.java:520)
at java.base/java.util.TimSort.mergeForceCollapse(TimSort.java:461)
at java.base/java.util.TimSort.sort(TimSort.java:254)
at java.base/java.util.Arrays.sort(Arrays.java:1441)
at com.hackerrank.Solution.luckBalance(Solution.java:15)
at com.hackerrank.Solution.main(Solution.java:49)

Looking at the answers above I tried adding a condition for equals and I don't know why but it worked. Hopefully we must explicitly specify what should be returned for all cases (greater than, equals and less than):

        Arrays.sort(contests, (row1, row2) -> {
if (row1[0] < row2[0]) {
return 1;
}
if(row1[0] == row2[0]) return 0;
return -1;
});

小开

I had the same symptom. For me it turned out that another thread was modifying the compared objects while the sorting was happening in a Stream. To resolve the issue, I mapped the objects to immutable temporary objects, collected the Stream to a temporary Collection and did the sorting on that.

小开

The origin of this exception is a wrong Comparator implementation. By checking the docs, we must implement the compare(o1, o2) method as an equivalence relation by following the rules:

if a.equals(b) is true then compare(a, b) is 0
if a.compare(b) > 0 then b.compare(a) < 0 is true
if a.compare(b) > 0 and b.compare(c) > 0 then a.compare(c) > 0 is true

You may check your code to realize where your implementation is offending one or more of Comparator contract rules. If it is hard to find it by a static analysis, you can use the data which cast the exception to check the rules.

小开

What about doing something simpler like this:

int result = card1.getSet().compareTo(card2.getSet())
if (result == 0) {
result = card1.getRarity().compareTo(card2.getRarity())
}
if (result == 0) {
result = card1.getId().compareTo(card2.getId())
}
if (result == 0) {
result = card1.getCardType().compareTo(card2.getCardType())
}
return result;

You just need to order the comparisons in order of preference.

小开

If you try to run this code you will meet the kind this exception:

    public static void main(String[] args) {
Random random = new Random();
List<Integer> list = new ArrayList<>();
for (int i = 0; i < 50000; i++) {
list.add(random.nextInt());
}
list.sort((x, y) -> {
int c = random.nextInt(3);
if (c == 0) {
return 0;
}
if (c == 1) {
return 1;
}
return -1;
});
}

Exception in thread "main" java.lang.IllegalArgumentException: Comparison method violates its general contract!
at java.util.TimSort.mergeLo(TimSort.java:777)
at java.util.TimSort.mergeAt(TimSort.java:514)
at java.util.TimSort.mergeCollapse(TimSort.java:441)
at java.util.TimSort.sort(TimSort.java:245)
at java.util.Arrays.sort(Arrays.java:1512)
at java.util.ArrayList.sort(ArrayList.java:1462)
at Test.main(Test.java:14)

The reason is when implementing the Comparator, it may meet the case of A > B and B > C and C > A and the sort method will be run around to be broken. Java prevent this case by throw exception this case:

class TimSort<T> {
.
.
.
else if (len1 == 0) {
throw new IllegalArgumentException(
"Comparison method violates its general contract!");
.
.
.

In conclusion, to handle this issue. You have to make sure the comparator will not meet the case of A > B and B > C and C > A.