比较方法违反了它的通用契约！

Question

能否简单地解释一下为什么这段代码会抛出异常“Comparison method violates its general contract!”，以及如何修复它？

private int compareParents(Foo s1, Foo s2) {
    if (s1.getParent() == s2) return -1;
    if (s2.getParent() == s1) return 1;
    return 0;
}

- n00bster

---

异常的名称和类是什么？它是IllegalArgumentException吗？如果我猜的话，我会认为你应该执行s1.getParent().equals(s2)而不是s1.getParent() == s2。 - Freiheit

还有被抛出的异常。 - Matthew Farwell

我对Java或Java比较API并不了解，但这种比较方法似乎是完全错误的。假设s1是s2的父节点，而s2不是s1的父节点。那么compareParents(s1, s2)等于0，但compareParents(s2, s1)却等于1。这没有意义。（此外，就像下面aix提到的那样，它也不具有传递性。） - mqp

该错误似乎只由特定库http://cr.openjdk.java.net/~martin/webrevs/openjdk7/timsort/src/share/classes/java/util/TimSort.java.html产生。 - Peter Lawrey

在Java中，您可以使用equals（返回布尔值）或compareTo（返回-1、0或+1）。覆盖Foo类中的这些函数后，您可以检查s1.getParent().equals(s2) ... - Mualig

异常是否抛出取决于所使用的JRE版本。Java6将允许此操作，而Java7和8将抛出错误。 - THelper

Answer 1

你的比较器不是可传递的。

假设A是B的父节点，B是C的父节点。由于A > B且B > C，因此必须有A > C。然而，如果将比较器应用于A和C，它将返回零，表示A == C。这违反了合同并因此引发异常。

库检测到这一点并通知您，而不是表现出不稳定的行为，这相当不错。

满足compareParents()中可传递性要求的一种方法是遍历getParent()链，而不仅仅查看直接祖先。

- NPE

---

Java 7引入了java.util.Arrays.sort方法。https://dev59.com/eGsz5IYBdhLWcg3wg4Gv - leonbloy

图书馆能够检测到这一点真是太棒了。Sun公司的某个人应该大声说“不用谢”。 - Qix - MONICA WAS MISTREATED

@Qix - 尽管我很喜欢Sun，但这是在Oracle旗下的Java 7中添加的。 - isapir

@Qix-MONICAWASMISTREATED 为了澄清历史，TimSort移植到Java是由曾在Sun工作的Josh Bloch编写的，当时他在Google工作，并且被Sun的人员整合到OpenJDK 7开发线中，时间是2009年7月。这是在Oracle加入之前。不过，Oracle负责发布JDK 7版本。JDK 7更改集 - 错误报告 - Stuart Marks

@isapir 请查看之前的评论。 - Stuart Marks

Answer 2

仅因为这是我谷歌此错误时得到的内容，我的问题是我有

if (value < other.value)
  return -1;
else if (value >= other.value)
  return 1;
else
  return 0;

显然，value >= other.value 的应该实际上是 value > other.value ，这样才能在对象相等时返回0。

- you786

---

我需要补充一点，如果你的value中有任何一个NaN（如果value是double或float类型），它也会失败。 - Matthieu

Answer 3

违反合同通常意味着比较器在比较对象时未提供正确或一致的值。例如，您可能希望执行字符串比较并强制空字符串按照末尾排序：

if ( one.length() == 0 ) {
    return 1;                   // empty string sorts last
}
if ( two.length() == 0 ) {
    return -1;                  // empty string sorts last                  
}
return one.compareToIgnoreCase( two );

但是这忽略了当一个和两个都为空的情况 - 在这种情况下，返回错误的值（1而不是0来表示匹配），比较器将其报告为违规。应该写成：

但是这忽略了当一个和两个都为空的情况 - 在这种情况下，返回错误的值（1而不是0来表示匹配），比较器将其报告为违规。应该写成：

if ( one.length() == 0 ) {
    if ( two.length() == 0 ) {
        return 0;               // BOth empty - so indicate
    }
    return 1;                   // empty string sorts last
}
if ( two.length() == 0 ) {
    return -1;                  // empty string sorts last                  
}
return one.compareToIgnoreCase( two );

- CESDewar

Answer 4

即使您的compareTo在理论上保持传递性，有时微妙的错误会搞砸一切……比如浮点数算术误差。我曾经遇到过这种情况，以下是我的代码：

即使你的compareTo在理论上保持了传递性，但有时微妙的bug会搞砸一切，比如浮点数算术误差。它曾经发生在我身上。这是我的代码：

public int compareTo(tfidfContainer compareTfidf) {
    //descending order
    if (this.tfidf > compareTfidf.tfidf)
        return -1;
    else if (this.tfidf < compareTfidf.tfidf)
        return 1;
    else
        return 0;

}   

可推性显然成立，但由于浮点数计算中的微小误差，我一直遇到IllegalArgumentException异常。实际上，由于舍入误差导致了本不应该出现错误的情况下，可推性被破坏了！因此，我重写了代码，考虑到0之间的微小差异，然后它就起作用了：

public int compareTo(tfidfContainer compareTfidf) {
    //descending order
    if ((this.tfidf - compareTfidf.tfidf) < .000000001)
        return 0;
    if (this.tfidf > compareTfidf.tfidf)
        return -1;
    else if (this.tfidf < compareTfidf.tfidf)
        return 1;
    return 0;
}   

- SomeGuy

---

这很有帮助！我的代码逻辑上没问题，但由于精度问题出现了错误。 - JSong

另一个想法是将它们装箱并延迟使用Double.compare。 - lcfd

Answer 5

在我们的情况下，我们之所以出现了这个错误，是因为我们不小心颠倒了s1和s2的比较顺序。所以要注意这一点。显然，实际情况比下面的例子要复杂得多，但这是一个说明：

s1 == s2   
    return 0;
s2 > s1 
    return 1;
s1 < s2 
    return -1;

- Uncle Iroh

Answer 6

编辑虚拟机配置对我有用。

-Djava.util.Arrays.useLegacyMergeSort=true

- Rishav Roy

---

请仔细检查我的格式化帮助是否有破坏任何东西。我不确定建议解决方案开头的“-”是否正确，或者您可能是想使用一项符号列表。 - Yunnosch

同时，请解释一下这如何有助于解决所描述的问题。目前它几乎只是一个代码答案。 - Yunnosch

Answer 7

我曾经在一段代码中看到过这种情况，其中经常需要检查 null 值：

if(( A==null ) && ( B==null )
  return +1;//WRONG: two null values should return 0!!!

- keesp

Answer 8

在我的情况下，我正在做以下事情：

if (a.someField == null) {
    return 1;
}

if (b.someField == null) {
    return -1;
}

if (a.someField.equals(b.someField)) {
    return a.someOtherField.compareTo(b.someOtherField);
}

return a.someField.compareTo(b.someField);

我忘记检查的是当a.someField和b.someField都为null时。

- jc12

Answer 9

如果 compareParents(s1, s2) == -1，那么期望 compareParents(s2, s1) == 1。但是你的代码并不总是符合这个要求。

具体来说，如果 s1.getParent() == s2 && s2.getParent() == s1，那么就可能会出现问题。

- Andrii Karaivanskyi

Answer 10

Java在严格意义上不检查一致性，只有在遇到严重问题时才会通知您。此外，它不会从错误中提供太多信息。

我对我的排序器发生的事情感到困惑，并制作了一个严格的consistencyChecker，也许这可以帮助你：

/**
 * @param dailyReports
 * @param comparator
 */
public static <T> void checkConsitency(final List<T> dailyReports, final Comparator<T> comparator) {
  final Map<T, List<T>> objectMapSmallerOnes = new HashMap<T, List<T>>();

  iterateDistinctPairs(dailyReports.iterator(), new IPairIteratorCallback<T>() {
    /**
     * @param o1
     * @param o2
     */
    @Override
    public void pair(T o1, T o2) {
      final int diff = comparator.compare(o1, o2);
      if (diff < Compare.EQUAL) {
        checkConsistency(objectMapSmallerOnes, o1, o2);
        getListSafely(objectMapSmallerOnes, o2).add(o1);
      } else if (Compare.EQUAL < diff) {
        checkConsistency(objectMapSmallerOnes, o2, o1);
        getListSafely(objectMapSmallerOnes, o1).add(o2);
      } else {
        throw new IllegalStateException("Equals not expected?");
      }
    }
  });
}

/**
 * @param objectMapSmallerOnes
 * @param o1
 * @param o2
 */
static <T> void checkConsistency(final Map<T, List<T>> objectMapSmallerOnes, T o1, T o2) {
  final List<T> smallerThan = objectMapSmallerOnes.get(o1);

  if (smallerThan != null) {
    for (final T o : smallerThan) {
      if (o == o2) {
        throw new IllegalStateException(o2 + "  cannot be smaller than " + o1 + " if it's supposed to be vice versa.");
      }
      checkConsistency(objectMapSmallerOnes, o, o2);
    }
  }
}

/**
 * @param keyMapValues 
 * @param key 
 * @param <Key> 
 * @param <Value> 
 * @return List<Value>
 */ 
public static <Key, Value> List<Value> getListSafely(Map<Key, List<Value>> keyMapValues, Key key) {
  List<Value> values = keyMapValues.get(key);

  if (values == null) {
    keyMapValues.put(key, values = new LinkedList<Value>());
  }

  return values;
}

/**
 * @author Oku
 *
 * @param <T>
 */
public interface IPairIteratorCallback<T> {
  /**
   * @param o1
   * @param o2
   */
  void pair(T o1, T o2);
}

/**
 * 
 * Iterates through each distinct unordered pair formed by the elements of a given iterator
 *
 * @param it
 * @param callback
 */
public static <T> void iterateDistinctPairs(final Iterator<T> it, IPairIteratorCallback<T> callback) {
  List<T> list = Convert.toMinimumArrayList(new Iterable<T>() {

    @Override
    public Iterator<T> iterator() {
      return it;
    }

  });

  for (int outerIndex = 0; outerIndex < list.size() - 1; outerIndex++) {
    for (int innerIndex = outerIndex + 1; innerIndex < list.size(); innerIndex++) {
      callback.pair(list.get(outerIndex), list.get(innerIndex));
    }
  }
}

- Martin

---

只需使用参数列表和比较器调用checkConsistency方法。 - Martin

你的代码无法编译。类Compare，Convert（以及可能还有其他）未定义。请使用自包含示例更新代码片段。 - Gili

你应该修复checkConsi(s)tency函数中的拼写错误并删除所有多余的@param声明，以使代码更易读。 - Roland Illig