Java 集合排序：比较方法违反了它的一般契约

Question

我知道它已被询问和回答了数百万次，但我仍然无法弄清楚为什么我在排序过程中收到违规问题。这是我的代码：

Collections.sort(sorted, new Comparator<MyObject>() {
    @Override
    public int compare(MyObject m1, MyObject m2) {
        // Actual energy comparison :-
        // THE higher the energy, the earlier in the list
        float delta = m1.getTotalEnergy() - m2.getTotalEnergy();

        if (delta > 0) {
            return 1;
        } else if (delta < 0) {
            return -1;
        } else {
            return 0;
        }
    }
});

我收到这个错误

java.lang.IllegalArgumentException: Comparison method violates its general contract!  
        at java.util.TimSort.mergeHi(TimSort.java:895)  
        at java.util.TimSort.mergeAt(TimSort.java:512)  
        at java.util.TimSort.mergeForceCollapse(TimSort.java:453)  
        at java.util.TimSort.sort(TimSort.java:250)  
        at java.util.Arrays.sort(Arrays.java:1512)  
        at java.util.ArrayList.sort(ArrayList.java:1454)  
        at java.util.Collections.sort(Collections.java:175)

有什么想法吗？

Answer 1

也许这会带来改变：

public int compare(Object m1, Object m2) {
    // Actual energy comparison :-
    // THE higher the energy, the earlier in the list
    float delta = ((MyObject)m1).getTotalEnergy() - ((MyObject)m2).getTotalEnergy();
....
}

Answer 2

假设 getTotalEnergy() return(s) float，您可以使用

return new Float(m1.getTotalEnergy()).compareTo(m2.getTotalEnergy());

使用 Float.valueOf(float) 可能稍微更有效，希望这更容易阅读。

Float f1 = Float.valueOf(m1.getTotalEnergy());
Float f2 = Float.valueOf(m2.getTotalEnergy());
return f1.compareTo(f2);

Answer 3

未参考 MyObject。我的猜测是比较器与 MyObject.equal.

不一致

即您违反的合同是：

(comparator.compare(mo1, mo2) == 0) == mo1.equals(mo2)

您的比较器会将具有相同浮点值的对象比较为相等，其中更复杂的比较器会给出排序，而 equals 方法会说对象不相等。或者您可能遇到相反的问题——equals 方法表示对象相等，而 compare 方法表示它们不同。

以下应该有效。

public int compare(MyObject m1, MyObject m2) {
    if (m1 == m2) return 0;
    if (m1 == null) return -1;
    if (m2 == null) return 1;
    if (m1.equals(m2)) return 0;

    int value = Float.compare(m1.getTotalEnergy(), m2.getTotalEnergy());
    if (value != 0) return value;

    // Warning, this line is not fool proof as unequal objects can have identical hash 
    // codes.
    return m1.hashCode() - m2.hashCode();
}

Answer 4

以下代码已经过 float、NaN 和 null 值测试。所有案件都得到正确处理。我为 MyObject class.

创建了 hashCode() 和 equals() 方法

结果：[null, 0.0, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, NaN]

SortObjectFloatProperty

package q28004269;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class SortObjectFloatProperty {
    public static void main(String[] args) {
        List<MyObject> sorted;

        sorted = create(1f, 4f, 6f, null, 8f, 5f, Float.NaN, 3f, 2f, 7f, 0f, 9f);

        Collections.sort(sorted, new Comparator<MyObject>() {
            @Override
            public int compare(MyObject m1, MyObject m2) {
                if (m1 == m2) return 0;
                if (m1 == null) return -1;
                if (m2 == null) return 1;
                if (m1.equals(m2)) return 0;
                int value = Float.compare(m1.getTotalEnergy(), m2.getTotalEnergy());
                if (value != 0) return value;
                return m1.hashCode() - m2.hashCode();
            }
        });

        System.out.println(sorted);
    }

    public static MyObject create(float totalEnergy) {
        return new MyObject(totalEnergy);
    }

    public static List<MyObject> create(Object ...values) {
        List<MyObject> objs = new ArrayList<SortObjectFloatProperty.MyObject>();
        for (int i = 0; i < values.length; i++) {
            if (values[i] instanceof Float) {
                objs.add(create((float) values[i]));
            } else {
                objs.add(null);
            }
        }
        return objs;
    }
}

我的对象

package q28004269;

public static class MyObject {
    private float totalEnergy;

    public float getTotalEnergy() {
        return totalEnergy;
    }

    public void setTotalEnergy(float totalEnergy) {
        this.totalEnergy = totalEnergy;
    }

    public MyObject() {
        this(0.0f);
    }

    public MyObject(float totalEnergy) {
        this.totalEnergy = totalEnergy;
    }

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + Float.floatToIntBits(totalEnergy);
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null) return false;
        if (getClass() != obj.getClass()) return false;
        MyObject other = (MyObject) obj;
        return !(Float.floatToIntBits(totalEnergy) != Float.floatToIntBits(other.totalEnergy));
    }

    @Override
    public String toString() {
        return Float.toString(totalEnergy);
    }
}

Answer 5

评论中对 NaN 值进行了一些讨论。这很重要，因为 NaN 违反了我们对浮点数比较的典型期望。例如，Double.NaN > 0.0和Double.NaN < 1.0都是假的！

这可能会导致排序抛出您遇到的异常。即使没有抛出异常，它也可能导致列表以错误的顺序结束排序。因此，您的排序比较器必须处理 NaN 值。幸运的是，库的内置比较（例如 Double.compare()）可以为您完成这项工作。这与 Double.compareTo() 具有相同的语义，只是盒装 Double 值不是必需的。有关详细信息，请参阅 documentation。简而言之，NaN 值被认为大于所有其他值（包括 +Inf），负零小于正零。

要在 Comparator 中为 sort 使用 Double.compare()，请执行以下操作：

Collections.sort(data, new Comparator<MyObject>() {
    public int compare(MyObject m1, MyObject m2) {
        return Double.compare(m1.getTotalEnergy(), m2.getTotalEnergy());
    }
});

如果您使用的是 Java 8，您可以这样做：

data.sort(Comparator.comparing(MyObject::getTotalEnergy));

要处理空值，请用 nullsFirst 或 nullsLast:

包裹比较器

data.sort(Comparator.nullsFirst(Comparator.comparing(MyObject::getTotalEnergy)));

Java 集合排序：比较方法违反了它的一般契约

Java Collections sort: Comparison method violates its general contract

java

sorting

collections

comparison

SortObjectFloatProperty

我的对象