S04-X07 · Comparable 与 Comparator：排序契约与一致性

排序接口看起来只有一行 int compare(...)，但它背后是一套数学契约。TimSort 假定这套契约成立，一旦违反，它抛出的那句 Comparison method violates its general contract! 既没有行号也没有具体数据，是所有 Java 报错里最难定位的一类。这篇从契约讲起，落到四个高频事故点。

1. `compareTo` 的四条契约

Comparable<T>.compareTo 与 Comparator<T>.compare 的规则完全相同（后者的语义是 compare(a,b) 对应 a.compareTo(b)）：

契约	数学表述	违反后的现象
符号性	`sign(x.compareTo(y)) == -sign(y.compareTo(x))`	排序结果不稳定，或抛 `IllegalArgumentException`
传递性	`x>y && y>z ⇒ x>z`	TimSort 抛契约违约异常
自反一致性	`x.compareTo(x) == 0`	去重异常，元素凭空消失
与 `equals` 一致	`x.compareTo(y)==0 ⇔ x.equals(y)`（强建议）	`TreeSet`/`TreeMap` 丢元素

合同还要求：compare 不能抛 ClassCastException（对不兼容类型应返回任意结果，虽然实践中很少做到），并且实现应当可重复——同一个输入多次调用结果相同。

合同里最容易被忽略的是传递性。看这段典型的"按优先级排序"：

// 违反传递性：当两个值的精度不同时，比较结果自相矛盾
list.sort((a, b) -> (int) (a.score - b.score));      // 相减溢出
list.sort((a, b) -> a.score > b.score ? 1 : -1);     // 相等时返回 -1，反符号性

第二行是重灾区：a == b 时它返回 -1，而 b == a 时同样返回 -1，于是 sign(x<y) == sign(y<x)，符号性被破坏。正确写法只有一种形态：

list.sort(Comparator.comparingInt(Item::score));     // 委托给标准构造

或者手写时严格三态：

Integer.compare(a.score, b.score)   // 推荐：不会溢出，三态正确
Long.compare(a.id, b.id)            // long 同理

(int)(a - b) 的问题不只是溢出（差值超过 Integer.MAX_VALUE 会翻转符号），还在于 a - b == 0 时返回 0 是对的，但一旦溢出，两个不相等的元素被判为相等，TreeSet 就会静默丢弃其中一个。

2. `TimSort` 为什么会抛契约违约

Arrays.sort(Object[]) 与 List.sort 在 JDK 7 之后用 TimSort：先找自然有序段（run），再按栈式规则归并。归并过程依赖"已排序段的边界元素必然不大于相邻段"这一不变量。当 compare 违反契约，这个不变量被破坏，TimSort 用一次显式检查把这个状况报出来：

java.lang.IllegalArgumentException: Comparison method violates its general contract!
    at java.base/java.util.TimSort.mergeHi(TimSort.java:499)
    at java.base/java.util.TimSort.mergeAt(TimSort.java:536)
    at java.base/java.util.TimSort.mergeCollapse(TimSort.java:484)
    at java.base/java.util.TimSort.sort(TimSort.java:245)

栈帧全部落在 TimSort 内部，调用链里看不到你的 lambda——这就是它难查的原因。定位手段只有一条：把比较器换成"逐对校验"的包装器，记录违约的那一对元素。

Comparator<Item> checked = (a, b) -> {
    int r = real.compare(a, b);
    if (Integer.signum(r) != -Integer.signum(real.compare(b, a))) {
        throw new IllegalStateException("asymmetric: " + a + " vs " + b);
    }
    return r;
};

注意 TimSort 的检查是机会性的：小数组（长度小于 32）走二元插入排序，可能不触发报错，于是同一个 bug 在开发环境的小数据集上不出现、上生产就炸。

3. `equals` 与 `compareTo` 不一致：`TreeSet` 去重异常

TreeSet 与 TreeMap 不用 hashCode/equals 判定重复，它们用 compare 的结果是否为 0。所以：

class User implements Comparable<User> {
    String id; String name;
    public int compareTo(User o) { return id.compareTo(o.id); }   // 只比 id
}
Set<User> set = new TreeSet<>();
set.add(new User("1", "A"));
set.add(new User("1", "B"));      // 被当成重复，静默丢弃
System.out.println(set.size());   // 1

而 new User("1","A").equals(new User("1","B")) 若按 id+name 实现，返回 false。于是同一个对象集合，放进 HashSet 有两个元素，放进 TreeSet 只有一个。List.contains 与 SortedSet.contains 也会给出不同答案。

集合	判等依据	不一致时的表现
`HashSet`/`HashMap`	`hashCode` + `equals`	正常按 `equals`
`TreeSet`/`TreeMap`	`compare == 0`	按 `compare`，与 `equals` 无关
`List.contains`	`equals`	正常
`Arrays.binarySearch`（对象数组）	`compare`（预排序后）	找不到实际存在的元素

结论：实现 Comparable 时，让 0 的判定与 equals 对齐；对不上就在文档里写明"与 equals 不一致"，并避开 TreeSet。Spring 与 Hibernate 的实体更要注意：id 在持久化前是 null，按 id 比较会让所有未保存的实体互相等，放进 TreeSet 立刻只剩一个。

4. `Comparator` 链式组合

Comparator.comparing(...).thenComparing(...) 返回的是组合器，每一步都是新对象，天然不可变、可复用。

Comparator<Order> c = Comparator
        .comparing(Order::status)                       // 自然序
        .thenComparing(Order::createdAt, Comparator.reverseOrder())
        .thenComparingInt(Order::priority)
        .thenComparing(Order::id);

构造	作用	注意
`thenComparing(...)`	前一项相等时再比	相等是"`compare == 0`"
`comparingInt/Long/Double`	避免装箱	优先用这个版本
`nullsFirst(cmp)` / `nullsLast(cmp)`	收容 `null`	必须包在最外层
`reversed()`	反转当前比较器	只反转到此为止
`Comparator.reverseOrder()`	反转自然序	用于 `comparing` 的第二个参数

性能上，comparingInt 与 comparing 的差别不是"风格"：后者把键装箱成 Integer，在千万级元素排序时是实打实的 GC 压力。

thenComparing 的一个坑：Comparator.comparing(Order::createdAt).thenComparing(...) 里若 createdAt 为 null，会抛 NullPointerException 而不是排在末尾。必须写成 comparing(Order::createdAt, Comparator.nullsLast(Comparator.naturalOrder()))。

5. `reversed()` 与 `reverseOrder()` 的区别

这两个名字相似，作用域完全不同：

写法	作用对象	结果
`cmp.reversed()`	当前比较器整体	把 `cmp` 的结果取反
`Comparator.reverseOrder()`	元素的自然序	等价于 `Comparable` 结果取反
`Collections.reverseOrder(cmp)`	给定比较器	等价于 `cmp.reversed()`

最容易错的是插入位置：

Comparator.comparing(Order::status).thenComparing(Order::createdAt).reversed()
// 整体反转：先按 status 降序，再按 createdAt 降序

Comparator.comparing(Order::status)
        .thenComparing(Order::createdAt, Comparator.reverseOrder())
// 只反转第二级：status 升序，createdAt 降序

第一行是"链尾调用"，reversed() 落在整条链上；想要只反转某一级，必须把反转放进那一级的比较器参数里。这个差别在调试时表现为"排序看起来对了一半"。

另外，reversed() 的实现是 Collections.reverseOrder(this)，它在比较时交换参数再取负；如果原比较器有副作用（极少见，但存在），reversed() 会让副作用顺序反过来。

6. 基本类型数组：不稳定的双轴快排

Arrays.sort 对两类数组用两套算法，这是稳定性的分水岭：

数组类型	算法	稳定性	最坏复杂度
`Object[]`、`List<T>`	TimSort	稳定	O(n log n)
`int[]`/`long[]`/`double[]` 等	双轴快速排序（Dual-Pivot Quicksort）	不稳定	O(n²)（极端退化）
`Arrays.parallelSort`	并行归并/TimSort	稳定（对象数组）	O(n log n)

Integer[] boxed = {3, 1, 2};
Arrays.sort(boxed);                    // TimSort，稳定
int[] prim = {3, 1, 2};
Arrays.sort(prim);                     // 双轴快排，不稳定

不稳定的含义是：键相等的元素，排序后相对顺序可能改变。对基本类型数组这不重要（值不可区分），但很多人为了"省一次装箱"把带索引的 int[] 当排序目标，再用另一个数组记住原始下标——这时顺序扰动就直接毁掉业务逻辑。要稳定就排对象数组，或用 Integer[] 加 Comparator。

parallelSort 在多核上对大于几千元素的数组更快，但代价是额外的合并开销；小数组用它会比串行还慢，阈值由 Arrays.MIN_ARRAY_SORT_GRAN（默认 8192）决定。

7. 排错

现象	原因	处理
`Comparison method violates its general contract!`	比较器破坏符号性或传递性	换成 `Integer.compare`，别用相减或三元
小数据不报错，生产报错	TimSort 对短数组不做同样的检查	用校验包装器在测试里跑大数据
`TreeSet` 里元素数少于预期	`compare == 0` 而 `equals == false`	让 0 的判定与 `equals` 对齐
排序键为 null 抛 NPE	未包 `nullsFirst/nullsLast`	把 null 处理放在最外层
`reversed()` 后整体乱序	调用位置在链尾，反转了整条链	把反转挪进对应级的参数
基本类型数组排序后下标错位	双轴快排不稳定	改排对象数组或保留原始索引

8. 边界

场景	建议	理由
类有天然唯一序（`BigDecimal`、版本号）	实现 `Comparable`	语义清晰，工具类直接可用
同一类型多种排序	只实现 `Comparable` 的一种，其余用 `Comparator`	避免语义冲突
海量数值排序	基本类型数组 + `parallelSort`	省装箱，利用多核
排序后要判重	`TreeSet` 且 `compare==0` 与 `equals` 对齐	否则丢数据
跨服务传输的比较规则	显式 `Comparator` 常量	避免各自实现不一致

9. 自测

a.compareTo(b) 与 b.compareTo(a) 都返回 -1，破坏了哪一条契约？
为什么 (int)(a - b) 作为比较结果会产生错误排序？有哪两个独立原因？
Comparison method violates its general contract! 的栈帧为什么不出现你的代码？怎么定位到具体元素？
同一个实体放进 HashSet 有两个，放进 TreeSet 只剩一个，该从哪里下手改？
comparing(A).thenComparing(B).reversed() 与 comparing(A).thenComparing(B, reverseOrder()) 结果差在哪？
int[] 与 Integer[] 分别用哪种排序算法，稳定性如何？

1. compareTo 的四条契约

2. TimSort 为什么会抛契约违约

3. equals 与 compareTo 不一致：TreeSet 去重异常

4. Comparator 链式组合

5. reversed() 与 reverseOrder() 的区别