Java自定义比较器违反通用契约异常问题排查咨询

问题背景 #

对一组层级格式的字符串排序时，抛出java.lang.IllegalArgumentException: Comparison method violates its general contract!异常。原始代码如下：

import org.apache.commons.lang3.StringUtils;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class ComparatorTest {

    public static void main(String[] args) {
        List<String> ll = List.of("1.A", "1.A.1", "10.A", "10.A.1", "10.A.2", "10.A.3", "12.A", "12.A.1", "12.A.2",
                "12.A.4", "12.A.6", "1A.2", "2.A.1", "2.A.1.b", "2.A.1.b.1", "2.A.1.b.2", "2.A.1.b.3", "20.A.1",
                "20.A.1.a", "20.A.1.b", "20.A.1.b.1", "20.A.1.b.2", "3.A.1", "3.A.1.a", "3.A.1.a.1", "3.A.1.a.2",
                "3.A.1.a.3", "3.A.1.a.4", "3.A.1.b", "3.A.10", "6.A.1", "9.A.1");
        
        ArrayList<String> l2 = new ArrayList<>(ll);
        Collections.sort(l2, (obj1, obj2) -> {
            try {
                String[] prodClass1 = obj1.split("\\.");
                String[] prodClass2 = obj2.split("\\.");
                for (int i = 0; (i < prodClass1.length) && (i < prodClass2.length); i++) {
                    if (!prodClass1[i].equals(prodClass2[i])) {
                        if (StringUtils.isNumeric(prodClass1[i]) && StringUtils.isNumeric(prodClass2[i])) {
                            return Integer.valueOf(prodClass1[i]).compareTo(Integer.valueOf(prodClass2[i]));
                        } else {
                            return prodClass1[i].compareToIgnoreCase(prodClass2[i]);
                        }
                    }
                }
                return obj1.compareToIgnoreCase(obj2);
            } catch (Exception e) {
                e.printStackTrace();
                return obj1.compareToIgnoreCase(obj2);
            }
        });
        System.out.println(l2);
    }
}

有意思的是，只要移除列表ll中的任意一个元素，代码就能正常运行。给比较器添加额外条件后，代码恢复正常，修改后的比较器代码：

Collections.sort(l2, (obj1, obj2) -> {
    try {
        String[] prodClass1 = obj1.split("\\.");
        String[] prodClass2 = obj2.split("\\.");
        for (int i = 0; (i < prodClass1.length) && (i < prodClass2.length); i++) {
            if (!prodClass1[i].equals(prodClass2[i])) {
                if (StringUtils.isNumeric(prodClass1[i]) && StringUtils.isNumeric(prodClass2[i])) {
                    return Integer.valueOf(prodClass1[i]).compareTo(Integer.valueOf(prodClass2[i]));
                } else if (StringUtils.isNumeric(prodClass1[i]) || StringUtils.isNumeric(prodClass2[i])) {
                    return StringUtils.isNumeric(prodClass1[i]) ? -1 : 1;
                } else {
                    return prodClass1[i].compareToIgnoreCase(prodClass2[i]);
                }
            }
        }
        return obj1.compareToIgnoreCase(obj2);
    } catch (Exception e) {
        e.printStackTrace();
        return obj1.compareToIgnoreCase(obj2);
    }
});

添加日志后的执行输出：

prodClass1: [3, A, 1, a, 1] Comparing with prodClass2: [2, A, 1, b, 3]
prodClass1: [2, A, 1, b, 3] Comparing with prodClass2: [3, A, 1, a]
prodClass1: [2, A, 1, b, 3] Comparing with prodClass2: [3, A, 1]
Exception in thread "main" java.lang.IllegalArgumentException: Comparison method violates its general contract!
    at java.base/java.util.TimSort.mergeHi(TimSort.java:903)
    at java.base/java.util.TimSort.mergeAt(TimSort.java:520)
    at java.base/java.util.TimSort.mergeForceCollapse(TimSort.java:461)
    at java.base/java.util.TimSort.sort(TimSort.java:254)
    at java.base/java.util.Arrays.sort(Arrays.java:1515)
    at java.base/java.util.ArrayList.sort(ArrayList.java:1750)
    at java.base/java.util.Collections.sort(Collections.java:179)
    at core.ComparatorTest.main(ComparatorTest.java:30)

问题根源：比较器违反传递性契约 #

Java排序算法（如TimSort）要求自定义比较器必须满足三个核心契约：

1. 自反性：compare(a,a)必须返回0
2. 对称性：compare(a,b)必须等于 -compare(b,a)
3. 传递性：如果compare(a,b) ≤ 0且compare(b,c) ≤ 0，则必须compare(a,c) ≤ 0

原始比较器的问题出在数字段与非数字段的混合比较逻辑，直接使用字典序比较会破坏传递性：
比如存在三个元素："1A.2"、"2.A.1"、"10.A"：

• 比较"1A.2"和"2.A.1"：第一段"1A"（非数字）和"2"（数字）用字典序比较，"1A" < "2"，返回-1
• 比较"2.A.1"和"10.A"：第一段都是数字，2 < 10，返回-1
• 按传递性，"1A.2"应该小于"10.A"，但实际比较时，"1A"和"10"字典序比较，"1A"的第二个字符是'A'，"10"是'0'，所以"1A" > "10"，返回1，直接违反传递性。

当列表中同时存在这类触发传递性冲突的三元组时，排序算法检测到契约违反，抛出异常；移除任意一个元素后，冲突三元组消失，因此不会触发异常。

修改后代码正常的原因 #

修改后的比较器新增了规则：只要两个分段中有一个是数字、另一个是非数字，直接让数字段排在非数字段前面。这一规则统一了数字与非数字的比较逻辑：

• 所有数字段的优先级高于非数字段
• 数字之间按数值大小比较，非数字之间按字典序比较

这样整个比较器完全满足排序算法要求的三个契约，因此不会再抛出异常，排序逻辑也更符合层级字符串的预期排序规则。

内容的提问来源于stack exchange，提问作者jos.mathew123