无法复制:"比较方法违反了其总合同!"

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%28int%2Cint%2Cint%2Cint% 29

Answer 1

从文档中compare.

实施者必须确保sgn(x.compareTo(y)) == -sgn(y.compareTo(x))所有x和y

基于减法的比较器不符合这种条件.这是因为减法可能会溢出.例如

Integer.MIN_VALUE - 0
0 - Integer.MIN_VALUE 

都是消极的.

你处理Dates 的方式也有问题.来自以下文件compare:

最后,实现者必须确保这x.compareTo(y)==0意味着sgn(x.compareTo(z)) == sgn(y.compareTo(z))对所有人而言z.

你的compare方法打破了这个.例如,如果x是null,y1970年1月1日,z1970年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);
} 

我设法重现了这个问题,但List至少只有s长度32.请参阅此链接以获取List至少为何需要尺寸的说明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> 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;
                }
            }
        }
    }
}