java.lang.IllegalArgumentException：比较方法违反其一般约定

java.lang.IllegalArgumentException: Comparison method violates its general contract

提问by Chandu

Hi below is my compare method of my comparator. I am not sure what is wrong. I looked up other similar titled questions and answers on stack overflow but not sure what is wrong with my method but I keep getting java.lang.IllegalArgumentException: Comparison method violates its general contract!

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

Any help will be greatly appreciated

任何帮助将不胜感激

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

Adding the exception I am getting

添加我得到的例外

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)

采纳答案by Rohit Jain

Your compare()method is not transitive. If A == Band B == C, then Amust be equal to C.

您的compare()方法不是可传递的。如果A == B和B == C，则A必须等于C。

Now consider this case:

现在考虑这种情况：

For A, B, and C, suppose the containsKey()method return these results:

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

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

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

Also, consider orders for A.getId()!= B.getId().

另外，请考虑A.getId()!= 的订单B.getId()。

So,

所以，

1. Aand Bwould return 0, as outer ifcondition will be false=> A == B
2. Band Cwould return 0, as outer ifcondition will be false=> B == C

1. A并且B会返回0，因为外部if条件将是false=>A == B
2. B并且C会返回0，因为外部if条件将是false=>B == C

But, Aand C, could return -1, or 1, based on your test inside the ifblock. So, A != C. This violates the transitivity principle.

但是, Aand C, 可能会返回-1, or 1，根据您在if块内的测试。所以，A != C。这违反了传递性原则。

I think, you should add some condition inside your elseblock, that performs check similar to how you do in ifblock.

我认为，您应该在else块中添加一些条件，执行类似于您在if块中所做的检查。

回答by chrylis -cautiouslyoptimistic-

I think the problem is in your default case. Consider the set of nodes A, B, and C, where the IDs are 'a', 'b', and 'c'. Consider further that your childMap, which contains the relative ordering information, has the following contents:

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

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

Now if you run your comparemethod on A and B, you return 0, indicating that A and B are equivalent. Further, if you compare B and C, you still return 0. However, if you compare A and C, then you return -1, indicating that A is smaller. This violates the transitivity property of the Comparatorcontract:

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

The implementor must also ensure that the relation is transitive: ((compare(x, y)>0) && (compare(y, z)>0))implies compare(x, z)>0.

Finally, the implementor must ensure that compare(x, y)==0implies that sgn(compare(x, z))==sgn(compare(y, z))for all z.

实现者还必须确保关系是可传递的：((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。

You can't treat "items which don't have an order assigned" as having the value "somewhere vaguely in the middle", since sorting algorithms don't know where to put them. If you want to stay with this approach, then in the case where the value is not present in the map, you need to assign a fixed value to be the ordering number; something like either 0or MIN_INTis a reasonable choice (but any choice needs to be documented in the Javadoc for compare!).

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