java.lang.IllegalArgumentException:比较方法违反了其一般合同

Question

嗨,下面是我比较器的比较方法.我不确定是什么问题.我在堆栈溢出时查找了其他类似的标题问题和答案,但不确定我的方法有什么问题,但我不断得到java.lang.IllegalArgumentException:比较方法违反了它的一般合同!

任何帮助将不胜感激

public int compare(Node o1, Node o2)
{
    HashMap<Integer,Integer> childMap = orderMap.get(parentID);
    if(childMap != null && childMap.containsKey(o1.getID()) && 
                           childMap.containsKey(o2.getID()))
    {
        int order1 = childMap.get(o1.getID());
        int order2 = childMap.get(o2.getID());

        if(order1<order2) 
            return -1;
        else if(order1>order2) 
            return 1;
        else 
            return 0;
    }
    else
        return 0;
}

添加我得到的例外

java.lang.IllegalArgumentException: Comparison method violates its general contract!
at java.util.TimSort.mergeLo(TimSort.java:747)
at java.util.TimSort.mergeAt(TimSort.java:483)
at java.util.TimSort.mergeCollapse(TimSort.java:410)
at java.util.TimSort.sort(TimSort.java:214)
at java.util.TimSort.sort(TimSort.java:173)
at java.util.Arrays.sort(Arrays.java:659)
at java.util.Collections.sort(Collections.java:217)

Answer 1

你的compare()方法不是传递性的.如果A == B和B == C,则A必须等于C.

现在考虑这种情况:

对于A,B和C,假设该containsKey()方法返回以下结果:

• childMap.containsKey(A.getID()) 回报 true
• childMap.containsKey(B.getID()) 回报 false
• childMap.containsKey(C.getID()) 回报 true

另外,考虑A.getId()!=的订单B.getId().

所以,

1. A和B将返回0,如外if条件将是false=>A == B
2. B和C将返回0,如外if条件将是false=>B == C

但是,A并且C,可以返回-1,或者1,基于您在if块内的测试.所以,A != C.这违反了传递性原则.

我认为,你应该在你的else块中添加一些条件,执行类似于你在if块中的操作.

Answer 2

我认为问题出在您的默认情况下。考虑节点集A，B，和C，这里的ID是'a'，'b'，和'c'。进一步考虑您的childMap，其中包含相关的订购信息，具有以下内容：

{ 'a' => 1, 'c' => 3 }

现在，如果您compare在A和B上运行方法，则返回0，表明A和B是等效的。此外，如果比较B和C，您仍然会返回0。但是，如果比较A和C，则返回-1，表示A较小。这违反了Comparator合同的可传递性：

实现者还必须确保该关系是可传递的：((compare(x, y)>0) && (compare(y, z)>0))暗含compare(x, z)>0。

最后，实现者必须确保compare(x, y)==0暗示sgn(compare(x, z))==sgn(compare(y, z))所有z。

您不能将“未分配订单的项目”视为值“模糊地位于中间”，因为排序算法不知道将其放在何处。如果您希望使用这种方法，那么在地图中不存在该值的情况下，您需要分配一个固定值作为订购号；像要么0或者MIN_INT是一个合理的选择（但任何选择需要的Javadoc文档记录在案compare！）。