比较法违反了它的一般契约! (在排序过程中，元素在集合中重复)

Question

我知道有很多主题是相同的，但这个案例在我看来有点不同，而且在javadocs中没有很好的记录。下面是代码。

Random random = new Random(0);

var list = new ArrayList<>();
for (int i = 0; i < 60; i++) {
    list.add(random.nextInt());
}

list.sort((x, y) -> {
    int sum = list.stream().reduce(0, Integer::sum);

    System.out.println(sum);

    return Integer.compare(x + sum, y + sum);
});

结果是异常。

-1303811196
-1303811196
.....
-1303811196
-1303811196
-1303811196
-1364558868
-1569607140
-1836181454
-2014724660
-2023409163
-2094470032
-2128134715
2107317277
2107317277
Exception in thread "main" java.lang.IllegalArgumentException: Comparison method violates its general contract!
    at java.base/java.util.TimSort.mergeLo(TimSort.java:781)
    at java.base/java.util.TimSort.mergeAt(TimSort.java:518)
    at java.base/java.util.TimSort.mergeCollapse(TimSort.java:448)
    at java.base/java.util.TimSort.sort(TimSort.java:245)
    at java.base/java.util.Arrays.sort(Arrays.java:1516)
    at java.base/java.util.ArrayList.sort(ArrayList.java:1717)
    at HomeWork6_4.Company.main(Company.java:131)

所以看起来，在排序过程中不可能依靠收集，因为它处于肮脏状态。这种行为在什么地方被记录下来了吗？

Answer 1

让我们通过记录比较器内部的工作来调试。为此，我添加了一个特殊的日志方法来跟踪比较器的结果。请检查下面的代码

 public static void main(String[] args) {
        Random random = new Random(0);

        var list = new ArrayList<Integer>();
        for (int i = 0; i < 60; i++) {
            list.add(random.nextInt());
        }
        list.sort(logging((x, y) -> {
        int sum= list.stream().reduce(0,Integer::sum);
            return Integer.compare(x+sum,y+sum);
        }));
    }




 public static Comparator<Integer> logging(Comparator<Integer> c)
        {
           return (Integer a,Integer b)-> {
               int r=c.compare(a,b);
           System.err.printf("%7d  %7d => %2d%n",a,b,r);
           return r;
           };
        }

比较器对两个输入(T a,T b)的行为如下。

(i) returns  less than 0 ,  means a<b
(ii)returns 0 , means a==b
(iii)return greater than 0 , means a>b

如果任何比较器不遵守这些规则，我们就说比较器坏了，现在让我们密切关注比较器的记录。

-723955400  -1155484576 => -1  // broken (a>b but comparator Integer.compare(a+sum,b+sum) returned less than 0)
1033096058  -723955400 =>  1   // broken 
1033096058  -1155484576 => -1
1033096058  -723955400 =>  1
-1690734402  1033096058 =>  1. // broken 

这表明你使用的特定比较器Integer.compare(a+sum,b+sum)已经过度膨胀，导致你对列表元素应用时结果不一致。当使用这样的破损比较器时，sort(c)会抛出这样的Exception。