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

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。

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; 
       } 
      } 
     } 
    } 
}