JDK排序异常-ComparisonMethodViolatesContract

hi，我是阿昌，今天记录一下JDK排序抛异常是怎么回事。

前言

线上偶尔会收到一个排序报错：

1	IllegalArgumentException: Comparison method violates its general contract!

这个异常到底怎么来的？下面直接用代码演示。

代码演示：怎么触发排序异常

演示一：违反自反性

从 JDK 1.7 开始，排序算法换成了 TimSort，它要求 compare 方法必须满足三个约束：

自反性：compare(x, y) 和 compare(y, x) 结果相反
传递性：x > y 且 y > z，则 x > z
对称性：x == y 时，x 与 z 的结果等于 y 与 z 的结果

违反任意一个，就会抛异常。下面这段代码就违反了自反性——当两个值相等时，正确应该返回 0，但它返回了 -1：

import java.util.*;

public class SortDemo {
    public static void main(String[] args) {
        List<Integer> list = Arrays.asList(
            1, 2, 3, 2, 2, 3, 2, 3, 2, 2, 3, 2, 3, 3, 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, 1, 1
        );

        Collections.sort(list, (o1, o2) -> o1 > o2 ? 1 : -1);
    }
}

运行直接抛异常：

Exception in thread "main" java.lang.IllegalArgumentException: 
    Comparison method violates its general contract!
    at java.util.TimSort.mergeHi(TimSort.java:899)
    at java.util.TimSort.mergeAt(TimSort.java:516)

compare(2, 2) 返回了 -1，而 compare(2, 2) 又返回 -1，两个相等元素互相比较都说自己”更小”，TimSort 检测到矛盾，直接报错。

演示二：long 强转 int 溢出（线上真实场景）

线上报错的代码长这样：

1 2	Collections.sort(tradeList, (o1, o2) -> (int) (o1.getAllowTime().getTime() - o2.getAllowTime().getTime()));

看起来没问题，但时间戳是 long，强转 int 可能溢出：

public class SortDemo2 {
    public static void main(String[] args) {
        long time1 = 1700000000000L;
        long time2 = time1 + 3_000_000_000L; // 差值 30 亿

        // long 差值: 3000000000
        System.out.println("long 差值: " + (time2 - time1));
        // 强转 int: -1294967296，变负数了！
        System.out.println("强转 int: " + (int)(time2 - time1));

        List<Long> times = Arrays.asList(time1, time2);
        Collections.sort(times, (o1, o2) -> (int)(o1 - o2));
    }
}

int 最大值只有 2147483647，差值超过这个范围就溢出变负数，排序逻辑乱套，极端情况下触发 TimSort 校验异常。

怎么修复

修复方案一：用 compareTo

Date.compareTo() 内部实现满足所有约束条件：

private void sortTradeByAllowTime(List<Trade> tradeList) {
    Collections.sort(tradeList, (o1, o2) -> 
        o1.getAllowTime().compareTo(o2.getAllowTime()));
}

修复方案二：Comparator.comparing（推荐）

Java 8 一行搞定，简洁又安全：

1
2
3

private void sortTradeByAllowTime(List<Trade> tradeList) {
    tradeList.sort(Comparator.comparing(Trade::getAllowTime));
}

总结

JDK 1.7+ 的 TimSort 会校验 compare 是否满足自反性、传递性、对称性，违反就抛异常。
long 强转 int 是隐形炸弹，数值溢出后排序结果不对，概率性触发异常。
排序用 compareTo 或 Comparator.comparing，别自己算差值再强转。