52

嗨，下面是我的比较器的比较方法。我不确定出了什么问题。我查找了有关堆栈溢出的其他类似标题的问题和答案，但不确定我的方法有什么问题，但我不断收到 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)
4

2 回答 2

68

你的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

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

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

于 2013-10-11T19:03:58.307 回答
7

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

{ '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！）。

于 2013-10-11T19:05:56.003 回答