Collections.sort传入Comparator时的高负载运行时异常排查

这是个非常典型的Java Comparator契约违反问题，咱们一步步拆解为什么会出现这种低负载正常、高负载炸锅的情况：

核心问题：错误的Comparator违反了排序算法依赖的契约 #

Java的Collections.sort()底层使用的是TimSort算法，它要求传入的Comparator必须严格遵守以下三大核心契约：

• 自反性：对于任意元素a，compare(a, a)必须返回0
• 对称性：如果compare(a, b) < 0，那么compare(b, a)必须> 0；如果compare(a, b) == 0，则compare(b, a)也必须== 0
• 传递性：如果compare(a, b) < 0且compare(b, c) < 0，那么compare(a, c)必须< 0

再看你最初的错误实现：

private static class CoordinateComparator implements Comparator<Coordinate> {
    @Override
    public int compare(Coordinate o1, Coordinate o2) {
        return o1.x <= o2.x ? -1 : 1;
    }
}

当o1.x == o2.x时，这个方法返回的是-1，而不是要求的0——这直接违反了自反性（自己和自己比较返回-1，完全不合理）和对称性（如果a.x == b.x，compare(a,b)返回-1，compare(b,a)也会返回-1，既不满足对称的正负相反，也不满足相等时的0返回）。

为什么低负载时没暴露问题？ #

低负载场景下，数据量小、相等元素少，TimSort的某些分支逻辑可能没被触发，比如不需要处理大量相等元素的归并、分区操作，即使契约有问题，也不会立刻引发可见的错误。但这种情况本质上是“侥幸”，代码本身已经存在严重的逻辑漏洞。

高负载时为什么会崩溃？ #

当数据量变大、相等元素增多时，TimSort会频繁依赖Comparator的契约来进行元素比较、分组、归并等操作。一旦契约被打破，算法会陷入逻辑混乱：比如无法正确判断元素的相等性，导致分区边界错误、归并时的索引越界，甚至触发无限循环，最终抛出运行时异常（比如IllegalArgumentException或者数组越界异常）。

为什么改用Integer.compareTo()就正常了？ #

Integer.compareTo()是完全遵守Comparator契约的实现：

• 当两个Integer相等时，返回0（满足自反性、对称性）
• 当o1.x < o2.x时返回-1，o1.x > o2.x时返回1（满足对称性、传递性）
  它完全符合排序算法的要求，所以不管负载高低，都能稳定工作。

内容的提问来源于stack exchange，提问作者Ashutosh Jha