一、背景
昨天在使用公司的某個(gè)平臺(tái)時(shí)，意外遇到了一個(gè)問(wèn)題：
Comparison method violates its general contract!
以前沒(méi)有見(jiàn)過(guò)這個(gè)異常，于是拿這個(gè)異常在網(wǎng)上搜了一下，發(fā)現(xiàn)是TimSort排序?qū)е碌?，這里簡(jiǎn)單記錄下。
二、復(fù)現(xiàn)+測(cè)試代碼
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)
報(bào)錯(cuò)異常：
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);
}
}
三、原因
查看下文檔，可以簡(jiǎn)單看出，這是JDK7與之前版本之間的一個(gè)小的兼容問(wèn)題。當(dāng)然，這個(gè)兼容性問(wèn)題也延續(xù)到了當(dāng)前的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
因?yàn)镴DK7以后，Arrays.sort方法換了排序方式，使用TimSort來(lái)進(jìn)行排序，新的實(shí)現(xiàn)在自定義比較器違背比較規(guī)則的情況下有可能會(huì)拋出異常，原來(lái)的實(shí)現(xiàn)則是忽略了這個(gè)異常。所以為了保證不拋出異常，對(duì)比較器的比較規(guī)則要求比較嚴(yán)格：
- 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))
簡(jiǎn)而言之，就是以下三個(gè)方面：
- 自反性：x與y的比較結(jié)果和y與x的比較結(jié)果相反；
- 傳遞性：如果x>y并且y>z, 那么 x>z；
- 對(duì)稱性：如果x=y, 那么x與z的比較結(jié)果和y與z的比較結(jié)果相同；
而如果需要使用JDK7之前的實(shí)現(xiàn)方式，可以通過(guò)增加系統(tǒng)屬性 java.util.Arrays.useLegacyMergeSort 恢復(fù)使用原來(lái)的排序規(guī)則。
PS：當(dāng)然這只是有可能出現(xiàn)IllegalArgumentException異常，并不是一定，這個(gè)取決于TimSort的內(nèi)部實(shí)現(xiàn)，這個(gè)可以看下源碼。
四、解決
解決方式自然也很簡(jiǎn)單：
- 增加系統(tǒng)屬性： java.util.Arrays.useLegacyMergeSort；
- 比較時(shí)，嚴(yán)格按照規(guī)則，盡量返回0，-1，1這三個(gè)標(biāo)準(zhǔn)結(jié)果來(lái)進(jìn)行比較。
代碼示例來(lái)源：
https://programtalk.com/java/comparison-method-violates-general-contract/
https://www.harinathk.com/java/sort-algorithm-changes-java-7-throws-illegalargumentexception/
