logo标签列表

Java错误：比较方法违反其通用合同。

javacomparemigrationjava-7comparator
121
我看到很多关于这个问题的提问，尝试解决了这个问题，但经过一小时的搜索和许多试错后，我仍然无法解决它。希望你们中的一些人能够发现问题所在。
这是我得到的：
java.lang.IllegalArgumentException: Comparison method violates its general contract!
    at java.util.ComparableTimSort.mergeHi(ComparableTimSort.java:835)
    at java.util.ComparableTimSort.mergeAt(ComparableTimSort.java:453)
    at java.util.ComparableTimSort.mergeForceCollapse(ComparableTimSort.java:392)
    at java.util.ComparableTimSort.sort(ComparableTimSort.java:191)
    at java.util.ComparableTimSort.sort(ComparableTimSort.java:146)
    at java.util.Arrays.sort(Arrays.java:472)
    at java.util.Collections.sort(Collections.java:155)
    ...

这是我的比较器：

@Override
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());

    if (card1.getSet() < card2.getSet()) {
        return -1;
    } else {
        if (card1.getSet() == card2.getSet()) {
            if (card1.getRarity() < card2.getRarity()) {
                return 1;
            } else {
                if (card1.getId() == card2.getId()) {
                    if (cardType > item.getCardType()) {
                        return 1;
                    } else {
                        if (cardType == item.getCardType()) {
                            return 0;
                        }
                        return -1;
                    }
                }
                return -1;
            }
        }
        return 1;
    }
}

有什么想法吗？

哪一行代码导致了这个异常的抛出？ComparableTimSort.java文件的第835和453行上是什么？ - Hovercraft Full Of Eels
2
@HovercraftFullOfEels 这是来自Oracle的一个类，不是我写的。它在那一行抛出了一个异常。这个方法非常长，看起来很难理解。 - Lakatos Gyula
我真的很好奇，是什么让你写出这样奇怪、不对称且难以阅读的“compareTo”函数？？？ - maaartinus
1
读完《Clean Code》这本书之后，我也不知道了。 - Lakatos Gyula
可能是重复的问题："Comparison method violates its general contract!" - Gili
显示剩余2条评论
13个回答
130

异常信息实际上已经很清楚了。它提到的是一个叫做传递性的契约：如果A > B并且B > C，那么对于任何A、B和C，都有A > C。我用纸和笔检查了一下，你的代码似乎有一些漏洞：

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

如果 card1.getRarity() > card2.getRarity()，则不要返回-1。

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

如果 id 不相等，返回 -1。如果两个 id 中哪一个更大，就返回对应的 -1 或 1。

看一下这个。除了更易读之外，我认为它实际上应该可以工作：

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!
17
实际上，您提供的示例并没有违反传递性，但是根据http://docs.oracle.com/javase/7/docs/api/java/util/Comparator.html#compare(T,%20T)中所述的规则sgn(compare(x, y)) == -sgn(compare(y, x))，这就是数学术语中的反对称性。 - Hans-Peter Störr
1
我建议使用 if (card1.getSet() != card2.getSet()) return card1.getSet() > card2.getSet() ? 1 : -1; 来提高速度，如果有人关心的话。 - maaartinus
我遇到了这个问题，这是我的比较器中的一个对称性问题。难以诊断的部分是我的弱点是第一个字段（一个布尔字段检查，而不是一个正确的比较），它没有检查两者都为真的情况。然而，只有在我添加了后续的下级比较之后，才会暴露出来，这可能会扰乱排序顺序。 - Thomas W
1
@maaartinus 谢谢你的建议！对我来说非常完美 :) - Sonhja
62
您可以使用以下类来定位比较器中的传递性错误：
/**
 * @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()
    {
    }
}

只需在失败的代码前调用Comparators.verifyTransitivity(myComparator, myCollection)即可。
5
这段代码验证了 compare(a,b) = - compare(b, c)。但它并没有检查如果 compare(a,b) > 0 && compare(b,c) > 0，则 compare(a,c) > 0。 - Olaf Achthoven
请注意，这可能非常慢。我们使用它时遇到了一些ANR问题。 - doctorram
42

这也与JDK的版本有关系。如果在JDK6中运行良好，那么可能会像你描述的在JDK7中出现问题，因为在jdk 7中的实现方法已经改变。

看这个：

描述：java.util.Arrays.sort（间接）使用的排序算法和 java.util.Collections.sort 已被替换。新的排序实现可能会抛出 IllegalArgumentException，如果它检测到违反 Comparable 协定的 Comparable 对象。以前的实现则会默默地忽略此类情况。如果需要以前的行为，可以使用新的系统属性 java.util.Arrays.useLegacyMergeSort 来恢复以前的归并排序行为。

我不知道确切的原因。但如果在使用 sort 之前添加代码，则没问题。

System.setProperty("java.util.Arrays.useLegacyMergeSort", "true");
13
这应该只是一个快速而丑陋的解决方法，可以让事情重新运作起来，直到你修复比较器。如果发生异常，这意味着你的比较器存在漏洞，排序顺序将会很奇怪。你必须考虑 http://docs.oracle.com/javase/7/docs/api/java/util/Comparator.html#compare(T,%20T) 中给出的所有规则。 - Hans-Peter Störr
如果“奇怪”正是我想要的呢？(a,b) -> { return (new int[]{-1,1})[(int)((Math.random()*2)%2)]} 我知道Collections.shuffle存在，但我不喜欢被过度保护。 - Jefferey Cave
我有一个旧应用程序，在使用JDK8时出现了这个错误。使用JDK6它可以正常工作，所以我只需降级到6，谢谢。 - Stefano Scarpanti
8
考虑以下情况：
首先，调用o1.compareTo(o2)。假设card1.getSet() == card2.getSet()为true，且card1.getRarity() < card2.getRarity()也为true，那么您将返回1。
接下来，调用o2.compareTo(o1)。同样，card1.getSet() == card2.getSet()为true。然后，您跳到下面的else，然后card1.getId() == card2.getId()恰好为true，并且cardType > item.getCardType()也是如此。您再次返回1。
由此可知，o1 > o2，同时o2 > o1。您违反了契约。
3

我有同样的症状。对我来说，问题在于另一个线程在Stream排序时修改了比较对象。为了解决这个问题，我将对象映射到不可变的临时对象上，将Stream收集到一个临时集合中，并在该集合上进行排序。

3
如果您尝试运行此代码，您将遇到以下异常：
    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)

理由是在实现比较器时，可能会遇到A>B、B>C和C>A的情况，sort方法就会在这种情况下不停地运行而导致失效。为了防止这种情况，Java会抛出异常：
class TimSort<T> {
.
.
.
else if (len1 == 0) {
            throw new IllegalArgumentException(
                "Comparison method violates its general contract!");
.
.
.

总之，要解决这个问题，您需要确保比较器不会遇到A > B且B > C且C > A的情况。

2
这个异常的起因是一个错误的Comparator实现。通过查看文档，我们必须按照以下规则实现compare(o1, o2)方法作为一种等价关系：
  • 如果 a.equals(b) 为true，则 compare(a,b) = 0
  • 如果 a.compare(b) > 0，则 b.compare(a) < 0 为true
  • 如果 a.compare(b) > 0 并且 b.compare(c) > 0，则 a.compare(c) > 0 为true

您可以检查代码以确定实现违反了哪个或多个Comparator契约规则。如果静态分析难以找到问题所在，可以使用导致异常的数据来检查规则。

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

然而，如果card2.getRarity()小于card1.getRarity()，你可能不会返回-1。

你同样会忽略其他情况。根据你的意图，我建议这样做：

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;

    }
}
1

我遇到了一个类似以下代码的错误：StockPickBean。它被从下面的代码中调用：

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);
    }
}

在遇到相同的错误后：

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

我改变了这一行：

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);

那修复了错误。

1

基于Gili的答案的一个变体，用于检查比较器是否满足compare方法JavaDoc中描述的要求-注重完整性和可读性，例如使用与JavaDoc中相同的变量名称。请注意，这是O（n ^ 3），仅在调试时使用，可能仅针对元素的子集，以便足够快地完成。

  public static <T> void verifyComparator(Comparator<T> comparator, Collection<T> elements) {
    for (T x : elements) {
      for (T y : elements) {
        for (T z : elements) {
          int x_y = comparator.compare(x, y);
          int y_x = comparator.compare(y, x);
          int y_z = comparator.compare(y, z);
          int x_z = comparator.compare(x, z);

          // javadoc: The implementor must ensure that sgn(compare(x, y)) == -sgn(compare(y, x))
          if (Math.signum(x_y) == -Math.signum(y_x)) { // ok
          } else {
            System.err.println("not holding: sgn(compare(x, y)) == -sgn(compare(y, x))" //
                + " | x_y: " + x_y + ", y_x: " + y_x + ",  x: " + x + ", y: " + y);
          }

          // javadoc: The implementor must also ensure that the relation is transitive:
          // ((compare(x, y)>0) && (compare(y, z)>0)) implies compare(x, z)>0.
          if (x_y > 0 && y_z > 0) {
            if (x_z > 0) { // ok
            } else {
              System.err.println("not holding: ((compare(x, y)>0) && (compare(y, z)>0)) implies compare(x, z)>0" //
                  + " | x_y: " + x_y + ", y_z: " + y_z + ",  x_z: " + x_z + ", x: " + x + ", y: " + y + ", z: " + z);
            }
          }

          // javadoc: Finally, the implementor must ensure that:
          // compare(x, y)==0 implies that sgn(compare(x, z))==sgn(compare(y, z)) for all z.
          if (x_y == 0) {
            if (Math.signum(x_z) == Math.signum(y_z)) { // ok
            } else {
              System.err.println("not holding: compare(x, y)==0 implies that sgn(compare(x, z))==sgn(compare(y, z)) for all z" //
                  + " | x_y: " + x_y + ", x_z: " + x_z + ",  y_z: " + y_z + ", x: " + x + ", y: " + y + ", z: " + z);
            }
          }
        }
      }
    }
  }
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接