只有在某些情况下才会抛出“比较方法违反其一般约定”

Question

首先，我知道这个问题在许多其他线程中都有描述。但是我无法找到并回答这个问题，为什么这个错误并不总是被抛出？

让我描述一下我的意思。我写了一些示例代码来说明这一点:

public class Mushroom {

    public int size;

    public Mushroom(int size) {
        this.size = size;
    }

    @Override
    public boolean equals(Object obj) {
        //this is intentionally false - read in description
        return false;
    }
}

DSA

public class MushroomComparator implements Comparator<Mushroom> {

    @Override
    public int compare(Mushroom o1, Mushroom o2) {
        // here is the code which breaks the contract
         if (o1.size < o2.size){
             return 1;
         }else if(o1.size >o2.size){
             return -1;
         }
         return 1;
    }

}

最后进行比较测试：

public class ComparisonTest {
    public static void main(String[] args) {
//      System.setProperty("java.util.Arrays.useLegacyMergeSort", "true");
    List<Mushroom> forest = new ArrayList<>();

        for(int i =0; i<18; i++){
            Mushroom mushroom1 = new Mushroom(1);
            Mushroom mushroom2 = new Mushroom(3);
            Mushroom mushroom3 = new Mushroom(2);

            forest.add(mushroom1);
            forest.add(mushroom2);
            forest.add(mushroom3);

        }
        Collections.sort(forest, new MushroomComparator());
    }
}

在运行时，我们会收到这个描述的问题

Java . lang . illegalargumentexception:比较法违反了它的通用契约！

根据托收文件。排序方法：

(可选)如果实现检测到列表元素的自然排序违反了可比协定

因此，让我们回答这个问题，这个合同在 Comparable 文档中是什么（在我的示例中，我使用 Comparator，但从文档中它应该满足相同的要求）

实现者必须确保所有 x 和 y 的 sgn（x.compareTo（y）） == -sgn（y.compareTo（x））

我故意打破这个规则来得到我所写的错误。这是compareTo方法的实现应该遵循的规则之一。其余的在文档中有描述，但是一般来说，我理解文档等价关系应该被满足

从比较契约中可以立即得出，商是C上的等价关系，自然排序是C上一个全序

现在真正困扰我的是我的测试方法中迭代数的变化。如果你把数字从18改为22，那么…异常将不会被抛出。这个异常被描述为可选的，所以它确实意味着有时这个异常会被抛出，有时不会。我没有深入研究排序算法（TimSort）的新实现（自Java7以来排序算法的变化）。我知道检查每组数据是否违反比较器契约可能会消耗一些CPU，但是什么是连接有时显示这一点，有时没有。这可能真的是误导。

此外，我可以将compare方法的实现更改为简单的..return 1。根据文档，它应该违反合同。但事实并非如此。在文档中还保留了一些关于合同的平等方法，但实际上并不需要

强烈建议但并非严格要求（x.compareTo（y）==0）==（x.equals（y））

为了在我的示例中检查它，我实现了equals方法以返回始终为假。有了这个，我确信equals方法不会对破坏比较器契约施加影响。

现在我的问题是：什么是真正的比较器契约（在破坏它的背景下）？为什么对于某些数据集，这个异常被抛出，而对于其他数据集，这个异常没有被抛出？也许我错过了什么？最后但同样重要的是——抛出这个异常需要打破哪些规则？

需要注意的是，这个问题的解决方案可能是关闭排序算法的这个新实现，这里描述了这个算法，并在我的示例代码中进行了注释。

Answer 1

事实上，如果＜code＞Collections，则总是抛出异常。sort（）有机会检测比较器的错误行为。这种情况发生在某些罕见的情况下，sort（）函数知道某个项目应该落在某个范围内，因为比较器之前已经指出了这一点，现在它正在调用比较器，并且被告知该项目应该落在此范围之外。但是sort（）非常复杂，它试图尽可能少地工作，因此检测这种错误行为的条件通常不会发生。

如果< code>sort()总是抛出异常，那么在开始对你的列表进行排序之前，它必须先发制人地调用你的比较器n^2(n的平方)次，以确保它总是对你的列表中的条目对的所有排列遵守它的约定。这将是极其低效的。

对比方必须遵守的合同见文件：(https://docs.oracle.com/javase/7/docs/api/java/util/Comparator.html)

>

实现者必须确保所有x和y的sgn（compare（x，y））==-sgn（比较（y，x））。

实现者还必须确保关系是可传递的：＜code＞（（compare（x，y）

最后，实现者必须确保compare（x，y）==0意味着sgn（compare，x））==sgn。

（其中 sgn（x） 是 'Math.signum（）' 函数。

Answer 2

为什么并不总是抛出此错误

因为验证您的比较方法不是 Collections.sort 的工作。它的工作只是实现排序。但是这样做的逻辑可以揭示无效的比较方法，作为其逻辑在某些条件分支中的副产品。在这种情况下，抛出而不是尝试继续使用无效的比较方法进行排序是有意义的。

什么是真正的比较者合同（在违反合同的情况下）？

如果你违反了合同，排序可能无法正常工作，或者根本无法正常工作。（并不是说它会验证您的比较方法。

为什么对于某些数据集会抛出此异常，而对于其他数据集则不会？

如果排序没有碰巧遵循导致排序代码可以检测到的逻辑缺陷的路径，则它不会知道抛出。但是正在使用的 TimSort 确实碰巧进入了一个逻辑分支，该分支揭示了无效的比较方法，因此它确实抛出了。