比较方法在比较java.util.Date时违反了它的通用契约。

Question

我遇到了以下错误：

Caused by: javax.faces.el.EvaluationException: java.lang.IllegalArgumentException: Comparison method violates its general contract!
    at javax.faces.component.MethodBindingMethodExpressionAdapter.invoke(MethodBindingMethodExpressionAdapter.java:101) [jboss-jsf-api_2.1_spec-2.1.28.SP1-redhat-1.jar:2.1.28.SP1-redhat-1]
    at com.sun.faces.application.ActionListenerImpl.processAction(ActionListenerImpl.java:101) [jsf-impl-2.1.28.redhat-10.jar:2.1.28.redhat-10]
    at javax.faces.component.UICommand.broadcast(UICommand.java:315) [jboss-jsf-api_2.1_spec-2.1.28.SP1-redhat-1.jar:2.1.28.SP1-redhat-1]
    at javax.faces.component.UIViewRoot.broadcastEvents(UIViewRoot.java:786) [jboss-jsf-api_2.1_spec-2.1.28.SP1-redhat-1.jar:2.1.28.SP1-redhat-1]
    at javax.faces.component.UIViewRoot.processApplication(UIViewRoot.java:1251) [jboss-jsf-api_2.1_spec-2.1.28.SP1-redhat-1.jar:2.1.28.SP1-redhat-1]
    at com.sun.faces.lifecycle.InvokeApplicationPhase.execute(InvokeApplicationPhase.java:81) [jsf-impl-2.1.28.redhat-10.jar:2.1.28.redhat-10]
    at com.sun.faces.lifecycle.Phase.doPhase(Phase.java:101) [jsf-impl-2.1.28.redhat-10.jar:2.1.28.redhat-10]
    at com.sun.faces.lifecycle.LifecycleImpl.execute(LifecycleImpl.java:118) [jsf-impl-2.1.28.redhat-10.jar:2.1.28.redhat-10]
    at javax.faces.webapp.FacesServlet.service(FacesServlet.java:593) [jboss-jsf-api_2.1_spec-2.1.28.SP1-redhat-1.jar:2.1.28.SP1-redhat-1]
    ... 29 more
Caused by: java.lang.IllegalArgumentException: Comparison method violates its general contract!
    at java.util.TimSort.mergeHi(TimSort.java:899) [rt.jar:1.8.0_65]
    at java.util.TimSort.mergeAt(TimSort.java:516) [rt.jar:1.8.0_65]
    at java.util.TimSort.mergeForceCollapse(TimSort.java:457) [rt.jar:1.8.0_65]
    at java.util.TimSort.sort(TimSort.java:254) [rt.jar:1.8.0_65]
    at java.util.Arrays.sort(Arrays.java:1512) [rt.jar:1.8.0_65]
    at java.util.ArrayList.sort(ArrayList.java:1454) [rt.jar:1.8.0_65]
    at java.util.Collections.sort(Collections.java:175) [rt.jar:1.8.0_65]

以下是我的比较方法代码。vo1.getAttribute()返回java.util.Date对象。

    @Override
    public int compare(DateComparableVO vo1, DateComparableVO vo2) {
        if (vo1 != null && vo1.getAttribute() != null && vo2 != null && vo2.getAttribute() != null) {
            return vo1.getAttribute().compareTo(vo2.getAttribute());
        }
        return -1;
    }

我的compare方法实现有问题吗？

如果出现null的情况。

为什么下面的代码可以正常工作而没有任何问题。

package test;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Date;
import java.util.List;

public class TestMain {

    public static void main(String[] args) {
        List<Employee> employees = new ArrayList<Employee>();
        employees.add(new Employee(new Date()));
        employees.add(null);
        employees.add(new Employee(new Date()));
        employees.add(new Employee(new Date()));
        employees.add(null);
        employees.add(new Employee(new Date()));
        employees.add(null);
        System.out.println(employees.size());
        Collections.sort(employees, new EmployeeComparator());

    }

}

class Employee {


    private Date attribute;

    public Employee() {
        // TODO Auto-generated constructor stub
    }

    public Employee(Date attribute) {
        this.attribute = attribute;
    }


    public Date getAttribute() {
        return attribute;
    }

    public void setAttribute(Date attribute) {
        this.attribute = attribute;
    }

    @Override
    public String toString() {
        return "Employee [attribute=" + attribute + "]";
    }
}

class EmployeeComparator implements Comparator<Employee>{

    @Override
    public int compare(Employee vo1, Employee vo2) {
        System.out.println("VO1 : " + vo1 + " VO2 : " + vo2);

        if (vo1 != null && vo1.getAttribute() != null && vo2 != null && vo2.getAttribute() != null) {
            return vo1.getAttribute().compareTo(vo2.getAttribute());
        }
        return -1;
    }

}

输出

7
VO1 : null VO2 : Employee [attribute=Fri Aug 18 11:51:11 SGT 2017]
VO1 : Employee [attribute=Fri Aug 18 11:51:11 SGT 2017] VO2 : null
VO1 : Employee [attribute=Fri Aug 18 11:51:11 SGT 2017] VO2 : Employee [attribute=Fri Aug 18 11:51:11 SGT 2017]
VO1 : Employee [attribute=Fri Aug 18 11:51:11 SGT 2017] VO2 : null
VO1 : Employee [attribute=Fri Aug 18 11:51:11 SGT 2017] VO2 : Employee [attribute=Fri Aug 18 11:51:11 SGT 2017]
VO1 : null VO2 : null
VO1 : null VO2 : Employee [attribute=Fri Aug 18 11:51:11 SGT 2017]
VO1 : null VO2 : Employee [attribute=Fri Aug 18 11:51:11 SGT 2017]
VO1 : Employee [attribute=Fri Aug 18 11:51:11 SGT 2017] VO2 : Employee [attribute=Fri Aug 18 11:51:11 SGT 2017]
VO1 : Employee [attribute=Fri Aug 18 11:51:11 SGT 2017] VO2 : Employee [attribute=Fri Aug 18 11:51:11 SGT 2017]
VO1 : null VO2 : null
VO1 : null VO2 : Employee [attribute=Fri Aug 18 11:51:11 SGT 2017]
VO1 : null VO2 : null

我是否在理解比较的过程中漏掉了一些重要部分？

- Jigar Naik

Answer 1

"contract"指的是比较函数必须定义一个“全序”。全序的要求之一是“非对称性”，这基本上意味着如果a < b，则b > a。在Java术语中，这意味着如果compare（a，b）（或a.compareTo（b））返回小于0的结果，则compare（b，a）（或b.compareTo（a））必须返回大于0的结果。您的比较函数不遵守此规则;如果x.getAttribute（）为非空，并且y.getAttribute（）为空，则compare（x，y）返回-1，而compare（y，x）也返回-1。TimSort有时会注意到这一点，并在发现未返回所期望的比较时引发异常。

另一种看待它的方式：如果输入中存在“特殊”值（除了如果您希望将对象视为“相等”，则顺序无关紧要），则必须预先决定您想要的顺序。假设您的输入包含其getAttribute（）为null的对象和其getAttribute（）为非null的对象。您希望具有空属性的对象出现在输出中的位置在哪里？您希望如何对它们进行排序？“我不在乎”不是选项。假设您希望所有具有空属性的对象都出现在最后，但您不关心空属性对象的排序方式。然后，您需要编写比较函数，以便：

- 具有非null属性的对象<具有null属性的对象； - 具有null属性的对象>具有非null属性的对象； - 具有null属性的两个对象被视为相等（比较函数返回0）。

如果您希望空值首先出现在数组中，则第一个和第二个点中的<和>将被颠倒。如果您希望基于某些其他属性对具有null属性的两个对象进行排序，那么请编写比较函数以实现此目的，但是您仍然需要决定具有null属性的对象相对于具有非null属性的对象出现在何处。也许无论您选择哪个都无所谓。但是你必须选择一些东西，并编写比较函数以根据你选择的内容返回结果。 P.S.: 没有特别的原因，解释为什么第二个带有 Employee 的代码片段能够工作而第一个不能。第二个案例中的比较器和第一个案例一样错误。然而，TimSort 不会查看每一对元素以确保比较符合契约（这将使其成为 O(n²) 算法）。我不熟悉 TimSort 的细节，但我怀疑它只在有理由比较两个元素以查看比较是否为（或许）<0 或 =0 时才进行此检查，并且它“知道”如果比较函数符合契约，则 >0 是不可能的。如果已经必须进行比较，则检查结果是否 >0 是相当便宜的，但我怀疑 TimSort 在没有必要时调用比较器，因为比较器的执行时间超出了它的控制范围。所以你的第二个示例之所以有效是因为“你很幸运”。

- ajb

Answer 2

在末尾的盲目-1表示null值不能被稳定处理（这会破坏归并排序算法）。您可以执行以下操作：

@Override
public int compare(DateComparableVO vo1, DateComparableVO vo2) {
    Date l = null, r = null;
    if (vo1 != null) {
        l = vo1.getAttribute();
    }
    if (vo2 != null) {
        r = vo2.getAttribute();
    }
    if (l == null && r == null) {
        return 0;
    } else if (l == null) {
        return -1;
    } else if (r == null) {
        return 1;
    }
    return l.compareTo(r);
}

- Elliott Frisch

Answer 3

除了其他答案已经指出的方法外，在Java 8中实现这种Comparator的另一种替代方法是使用静态工厂方法进行组合，例如：

Comparator<DateComparableVO> c = Comparator.nullsLast(
    Comparator.comparing(DateComparableVO::getAttribute,
        Comparator.nullsLast(Date::compareTo)));

根据您对空值的处理方式，可以选择使用nullsFirst或nullsLast。这可能是一个讨论的问题，但它清晰地说明了有关空值的预期行为。

如果您知道对象本身和属性都不可能存在任何空值，则可以简化为：

Comparator<DateComparableVO> c = Comparator.comparing(DateComparableVO::getAttribute);

当遇到null值时，会抛出NullPointerException。

- Hulk