java - 无法复制 : "Comparison method violates its general contract!"

Question

我收到以下错误:“比较方法违反了它的一般契约(Contract)!”使用以下比较器时，但是我无法使用 jUnit 复制异常。我想知道是什么导致了这个问题以及如何复制它。有其他人遇到同样问题但不知道如何复制的例子。

public class DtoComparator implements Comparator<Dto> {

    @Override
    public int compare(Dto r1, Dto r2) {

        int value = 0;

        value = r1.getOrder() - r2.getOrder();

        if (value == 0 && !isValueNull(r1.getDate(), r2.getDate()))
            value = r1.getDate().compareTo(r2.getDate());

        return value;
    }

    private boolean isValueNull(Date date, Date date2) {
        return date == null || date2 == null;
    }
}

调用代码时使用:

Collections.sort(dtos, new DtoComparator());

感谢您的帮助。

额外信息: 该错误似乎发生在 Java utils 中的 TimSort 类和名为 mergeLo 的方法中。 链接:http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/8-b132/java/util/TimSort.java#TimSort.mergeLo%28int%2Cint%2Cint%2Cint%29

Answer 1

来自compare的文档。

The implementor must ensure sgn(x.compareTo(y)) == -sgn(y.compareTo(x)) for all x and y

基于减法的比较器不满足此条件。这是因为减法会溢出。例如

Integer.MIN_VALUE - 0
0 - Integer.MIN_VALUE 

都是负数。

您处理 Date 的方式也有问题。来自 compare 的文档:

Finally, the implementor must ensure that x.compareTo(y)==0 implies that sgn(x.compareTo(z)) == sgn(y.compareTo(z)), for all z.

您的compare 方法打破了这一点。例如，如果 x 为 null，y 为 1970 年 1 月 1 日，z 为 1970 年 1 月 2 日，则

compare(x, y) == 0  // x == null
compare(x, z) == 0  // x == null
compare(y, z) == -1 // January 1st is before January 2nd.

我会这样写方法:

@Override
public int compare(Dto r1, Dto r2) {

    int value = Integer.compare(r1.getOrder(), r2.getOrder());
    if (value != 0)
        return value;
    Date date1 = r1.getDate();
    Date date2 = r2.getDate();
    if (date1 == null && date2 == null)
        return 0;
    if (date1 == null)
        return -1;
    if (date2 == null)
        return 1;
    return date1.compareTo(date2);
} 

我已设法重现该问题，但仅限于长度至少为 32 的 List。请参阅此链接以了解为什么需要大小至少为 32 的 List 的解释。 Why does this program using Collections.sort only fail for lists of size 32 or more?

public class Main {

    private static final class NumAndDate {
        private final int num;
        private final Date date;

        NumAndDate(int num, Date date) {
            this.num = num;
            this.date = date;
        }
    }

    public static final class NumAndDateComparator implements Comparator<NumAndDate> {

        @Override
        public int compare(NumAndDate r1, NumAndDate r2) {

            int value = 0;

            value = r1.num - r2.num;

            if (value == 0 && !isValueNull(r1.date, r2.date))
                value = r1.date.compareTo(r2.date);

            return value;
        }

        private boolean isValueNull(Date date, Date date2) {
            return date == null || date2 == null;
        }
    }

    public static void main(String[] args) {
        NumAndDate[] array = {
                new NumAndDate(0, new Date(0)),
                new NumAndDate(0, new Date(1)), 
                new NumAndDate(0, null)
        };
        Random random = new Random();
        for (int i = 0; i < 100; i++) {
            for (int j = 0; j < 10000; j++) {
                List<NumAndDate> list = new ArrayList<>();
                int[] arr = new int[i];
                for (int k = 0; k < i; k++) {
                    int rand = random.nextInt(3);
                    arr[k] = rand;
                    list.add(array[rand]);
                }
                try {
                    Collections.sort(list, new NumAndDateComparator());
                } catch (Exception e) {
                    System.out.println(arr.length + " " + Arrays.toString(arr));
                    return;
                }
            }
        }
    }
}