比较方法在比较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() returns 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;
    }

我实现的比较方法有什么问题吗？

在空场景的情况下。

为什么下面的代码没有任何问题。

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

我是否遗漏了理解比较的一些重要部分

Answer 1

末尾的盲目 -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);
}

Answer 2

比较的"contract"就是比较函数要定义一个全序。总顺序的要求之一是"asymmetry"，这基本上意味着如果a < b，则b > a。在 Java 术语中，这意味着如果 compare(a,b)（或 a.compareTo(b)）return 的结果 < 0，则 compare(b,a)（或 b.compareTo(a)）必须return 结果 > 0。您的比较函数不遵守此规则；如果 x.getAttribute() 非空且 y.getAttribute() 为空，则 compare(x,y) returns -1 和 compare(y,x) 也 returns -1。 TimSort 有时会注意到这一点，并在发现不符合 return 预期的比较时抛出异常。

另一种看待它的方式：如果输入中有 "special" 值，您必须事先决定您希望事物的顺序（除非您希望将对象比较为 "equal"，顺序无关紧要）。假设您的输入包含 getAttribute() 为空的对象，以及 getAttribute() 为非空的对象。您希望具有 null 属性的那些出现在输出中的什么位置？您希望如何订购它们？ "I don't care" 不是一个选项。 假设您希望所有空属性对象排在最后，但您不关心空属性对象的排序方式。然后你需要写你的比较函数，这样

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

如果想让null先出现在数组中，那么前两点的<和>就可以颠倒过来。如果您希望两个具有 null 属性的对象根据其他一些属性进行排序，那么编写您的比较函数以便它这样做，但是您仍然需要确定具有 null 属性的对象相对于具有 null 属性的对象出现的位置非空属性。也许你选择哪一个并不重要。但是你必须选择一些东西，你必须根据你选择的内容将你的比较函数写到 return 结果。

P.S.: 没有特别的原因可以解释为什么带有 Employee 的第二个代码片段有效而第一个无效。第二种情况下的比较器与第一种情况下的比较器一样错误。但是，TimSort 不会查看每一对元素以确保比较符合约定（这将使其成为 O(n²) 算法）。我不熟悉 TimSort 的细节，但我怀疑它只在有理由比较两个元素以查看比较是否（可能）<0 或 =0 时才进行此检查，并且它 "knows" 如果比较函数满足约定，则 >0 不应该是可能的。如果已经必须进行比较，则检查 >0 的结果非常便宜，但我怀疑 TimSort 在不需要时调用比较器，因为比较器的执行时间超出了它的控制范围。所以你的第二个例子起作用的基本原因是 "you got lucky".

Answer 3

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

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

或 nullsFirst，具体取决于您希望如何处理空值。这是否更具可读性可能是一个讨论问题，但它是自我记录的关于空值的预期行为是什么。

如果您知道不能有任何空值，无论是对象本身还是属性，都可以简化为

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

当遇到空值时会抛出 NullPointerException。

比较方法在比较java.util.Date时违反了它的一般契约

Comparison method violates its general contract while comparing java.util.Date

java

date

comparator

illegalargumentexception