一、背景
昨天在使用公司的某个平台时，意外遇到了一个问题：
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的内部实现，这个可以看下源码。
四、解决
解决方式自然也很简单：
- 增加系统属性： java.util.Arrays.useLegacyMergeSort；
- 比较时，严格按照规则，尽量返回0，-1，1这三个标准结果来进行比较。
代码示例来源：
https://programtalk.com/java/comparison-method-violates-general-contract/
https://www.harinathk.com/java/sort-algorithm-changes-java-7-throws-illegalargumentexception/
