解决 Comparison method violates its general contract!

一、背景

昨天在使用公司的某个平台时，意外遇到了一个问题：

Comparison method violates its general contract!

以前没有见过这个异常，于是拿这个异常在网上搜了一下，发现是 TimSort 排序导致的，这里简单记录下。

二、复现 + 测试代码

JDK 版本：

**

master@jiangmufeng ~ $ java -version
java version "1.8.0_191"
Java(TM) SE Runtime Environment (build 1.8.0_191-b12)
Java HotSpot(TM) 64-Bit Server VM (build 25.191-b12, mixed mode)

报错异常：

**

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:1438)
    at java.util.Arrays$ArrayList.sort(Arrays.java:3895)
    at java.util.Collections.sort(Collections.java:175)
    at sort.test.Main.sort(Main.java:31)
    at sort.test.Main.main(Main.java:21)

代码示例：

**

/**
 * Test TimSort
 * @author jiangmufeng
 * @date 2020-02-25 14:24
 **/
public class Main {
    public static void main(String[] args) {

        sort(1, 1, 1, 1, 1, 2, 1, 1, 1);
        sort(3, 2, 3, 2, 1, 31);
        sort(2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3);

        // exception
        sort(1, 2, 3, 2, 2, 3, 2, 3, 2, 2, 3, 2, 3, 3, 2, 2, 2, 2, 2, 2, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
                1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1);

    }

    private static void sort(Integer... ints) {
        List<Integer> list = Arrays.asList(ints);
        list.sort((o1, o2) -> {
            if (o1 < o2) {
                return -1;
            } else {
                return 1;
            }
        });
        System.out.println(list);
    }
}

三、原因

查看下文档，可以简单看出，这是 JDK7 与之前版本之间的一个小的兼容问题。当然，这个兼容性问题也延续到了当前的 JDK8 版本：

Area: API: Utilities

Synopsis: Updated sort behavior for Arrays and Collections may throw an IllegalArgumentException

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 behavior.

Nature of Incompatibility: behavioral

RFE: 6804124

如果有兴趣，可以看下以下链接（Java SE 7 and JDK 7 Compatibility）：https://www.oracle.com/technetwork/java/javase/compatibility-417013.html

因为 JDK7 以后，Arrays.sort 方法换了排序方式，使用 TimSort 来进行排序，新的实现在自定义比较器违背比较规则的情况下有可能会抛出异常，原来的实现则是忽略了这个异常。所以为了保证不抛出异常，对比较器的比较规则要求比较严格：

• sgn(x.compareTo(y)) == -sgn(y.compareTo(x))
• (x.compareTo(y)>0 && y.compareTo(z)>0) implies x.compareTo(z)>0
• x.compareTo(y)==0 implies that sgn(x.compareTo(z)) == sgn(y.compareTo(z))

简而言之，就是以下三个方面：

• 自反性：x 与 y 的比较结果和 y 与 x 的比较结果相反；
• 传递性：如果 x>y 并且 y>z, 那么 x>z；
• 对称性：如果 x=y, 那么 x 与 z 的比较结果和 y 与 z 的比较结果相同；

而如果需要使用 JDK7 之前的实现方式，可以通过增加系统属性 java.util.Arrays.useLegacyMergeSort 恢复使用原来的排序规则。

PS：当然这只是有可能出现 IllegalArgumentException 异常，并不是一定，这个取决于 TimSort 的内部实现，这个可以看下源码。

四、解决

解决方式自然也很简单：

1. 增加系统属性： java.util.Arrays.useLegacyMergeSort；
2. 比较时，严格按照规则，尽量返回 0，-1，1 这三个标准结果来进行比较。

代码示例来源：

https://programtalk.com/java/comparison-method-violates-general-contract/

https://www.harinathk.com/java/sort-algorithm-changes-java-7-throws-illegalargumentexception/

作者：骑着乌龟去看海
链接：https://www.jianshu.com/p/4e568ef541ae
来源：简书
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。