无法复制：“比较方法违反了其总合同！

Question

我收到以下错误：“比较方法违反了它的一般合同！”当使用下面的比较器时，我无法使用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（整型，整型，整数，整型）

Answer 1

从的文档中比较。

实施者必须确保< code > SGN(x . compare to(y))= =-SGN(y . compare to(x))对于所有< code>x和< code>y

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

Integer.MIN_VALUE - 0
0 - Integer.MIN_VALUE 

都是负面的。

在< code>compare的文档中，您处理< code>Date的方式也有问题:

最后，实施者必须确保< code>x.compareTo(y)==0意味着< code > SGN(x . compare to(z))= = SGN(y . compare to(z))，对于所有< code>z。

您的比较方法打破了这一点。例如，如果 x 为空，则 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 的列表。有关为什么需要大小至少为 32 的列表的说明，请参阅此链接。为什么这个程序使用 Collections.sort 只对大小为 32 或更大的列表失败？

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> html" target="_blank">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;
                }
            }
        }
    }
}