Collections.sort() 比较方法在Java中违反了它的一般契约

Question

我知道这种问题已经被问过数百万次甚至数十亿次，但是我还找不到答案:)

这个compare()方法没有Long,Double,Float,...,只有Date,boolean 和 Null 检查器，但是它告诉我 contract violation error，有人可以帮忙吗？

Collections.sort(users, new Comparator<MiniUser>() {
        @Override
        public int compare(MiniUser u1, MiniUser u2) {
            boolean resComing = checkMatchConditions(u1,user);
            boolean resExists = checkMatchConditions(u2,user);

            if(Boolean.valueOf(resComing) && Boolean.valueOf(resExists)) {
                if(u1.getLastMatchDate() == null){
                    return -1;
                }else if(u2.getLastMatchDate() ==null ){
                    return 1;
                }else if (u1.getLastMatchDate().toInstant().isBefore(u2.getLastMatchDate().toInstant())){
                    return -1;
                }else {
                    return 1;
                }
            }

            else if (Boolean.valueOf(resComing)) {
                return -1;
            }
            return 1;
        }

    });

MiniUser.class

public class MiniUser implements Serializable {

    String id;
    String name;
    Date lastMatchDate;
    boolean showCompleteName;

//getters, setters
}

checkMatchConditions return 基于一些计算的布尔值

Answer 1

您应该先阅读 JavaDoc of Comparator.compare() 以了解 "contract" 是什么：

The implementor must ensure that sgn(compare(x, y)) == -sgn(compare(y, x)) for all x and y.

在正常情况下，它表示如果 "x is greater than y, y must be smaller than x"。听起来很明显，但在您的比较器中并非如此：

在您的情况下，当两个用户拥有 checkMatchConditions false 时，您就违反了它，在这种情况下，compare(u1, u2) 和 compare(u2, u1) 都是 return 1。因此，有些情况下 u1 大于 u2，并且 u2 大于 u1，这是违规的。
同理，如果两个User都有checkMatchConditionstrue，而他们的lastMatchDates都是null，也属于违约
此外，因为您手动尝试将日期与 isBefore 进行比较，所以当两个用户有 checkMatchConditions true 和他们 lastMatchDates 都相等。

为了解决这个问题，您应该首先添加一个自然语言描述，说明您希望如何对用户进行排序。然后你可以计算出比较器逻辑。

顺便说一句，错误与Boolean.valueOf()无关。

既然您已经解释了要如何订购，请看一下这个比较器：

public int compare(MiniUser u1, MiniUser u2)
{
    // order by match
    boolean u1Matches = checkMatchConditions(u1, user);
    boolean u2Matches = checkMatchConditions(u2, user);

    if (u1Matches != u2Matches)
    {
        // put matching ones first
        return u1Matches ? -1 : 1;
    }
    else if (u1Matches)
    {
        // order by dates
        boolean u1HasDate = u1.getLastMatchDate() != null;
        boolean u2HasDate = u2.getLastMatchDate() != null;

        if (u1HasDate != u2HasDate)
        {
            // put the ones without date first
            return u1HasDate ? 1 : -1;
        }
        else if (u1HasDate)
        {
            // order chronologically
            return u1.getLastMatchDate().compareTo(u2.getLastMatchDate());
        }
        else
        {
            // no dates, no order possible
            return 0;
        }
    }
    else
    {
        // both don't match, no order possible
        return 0;
    }
}

如果我正确理解了您的要求，这应该会对您的元素施加一致的顺序。请注意我是如何使用 Date 的 compareTo 进行日期排序而不是自己做的，以及我如何 return 0 以防他们是 "equal"按顺序而不是 "randomly" returning 1 或 -1.

Answer 2

您需要找到 sgn(compare(x, y)) == -sgn(compare(y, x)) 不成立的地方。我建议你使用暴力查找示例。

Comparator<MiniUser> comp = ...
for (MiniUser a : users) {
    for (MiniUser b: users) {
         if (a == b) continue;
         if (comp.compare(a, b) != -comp.compare(b, a)) {
            // print an error message with these two.
         }
    }
}

Collections.sort() 比较方法在Java中违反了它的一般契约

Collections.sort() Comparison method violates its general contract in Java

java

sorting

collections

comparator

code-contracts