java 使用 Comparable 比较对象并在 TreeMap 中对它们进行排序

Using Comparable to compare objects and sorting them in a TreeMap

提问by arjacsoh

II cannot understand how should the natural ordering of class be "consistent with equals" when implementing the Comparableinterface. I detected a flaw in my program and therefore I checked it in the documentantion of the interface Comparable. My problem is that although two Objects are considered as distinct on the base of equals method, the TreeMap structure treats them as equal and consequently does not accept the second insert. The sample code is:

我无法理解在实现Comparable接口时，类的自然顺序应该如何“与等号一致” 。我在我的程序中检测到一个缺陷，因此我在接口Comparable的文档中检查了它。我的问题是，尽管在 equals 方法的基础上两个对象被认为是不同的，但 TreeMap 结构将它们视为相等，因此不接受第二个插入。示例代码是：

public class Car  implements Comparable<Car> {

 int weight;
 String name;

public Car(int w, String n) {
    weight=w;
    name=n;
}

public boolean equals(Object o){
    if(o instanceof Car){
        Car d = (Car)o;
        return ((d.name.equals(name)) && (d.weight==weight));
    }
    return false;

}

public int hashCode(){
    return weight/2 + 17;
}

public String toString(){
    return "I am " +name+ " !!!";
}


public int compareTo(Car d){
    if(this.weight>d.weight)
        return 1;
    else if(this.weight<d.weight)
        return -1;
    else
        return 0;
}

/*public int compareTo(Car d){
    return this.name.compareTo(d.name);
}*/

}



public static void main(String[] args) {
    Car d1 = new Car(100, "a");
    Car d2 = new Car(110, "b");
    Car d3 = new Car(110, "c");
    Car d4 = new Car(100, "a");

    Map<Car, Integer> m = new HashMap<Car, Integer>();
    m.put(d1, 1);
    m.put(d2, 2);
    m.put(d3, 3);
    m.put(d4, 16);

    for(Map.Entry<Car, Integer> me : m.entrySet())
    System.out.println(me.getKey().toString() + " " +me.getValue());

    TreeMap<Car, Integer> tm = new TreeMap<Car, Integer>(m);
    System.out.println("After Sorting: ");
    for(Map.Entry<Car, Integer> me : tm.entrySet())
        System.out.println(me.getKey().toString() + " " +me.getValue());
}

The output is :

输出是：

I am a !!! 16

I am c !!! 3

I am b !!! 2

After Sorting: 

I am a !!! 16

I am c !!! 2

That is, that the object c has replaced (somewhat) object b. If I comment the original equals method and uncomment the second equals method, which compares the objects according name, the output is the expected:

也就是说，对象 c 已经替换了（在某种程度上）对象 b。如果我注释原始 equals 方法并取消注释第二个 equals 方法，该方法根据名称比较对象，则输出是预期的：

I am a !!! 16

I am c !!! 3

I am b !!! 2

After Sorting: 

I am a !!! 16

I am b !!! 2

I am c !!! 3

Why does it come around in this way and what should I alter in order to insert and sort different objects with some attributes of equal value in a TreeMap?

为什么它会以这种方式出现，为了在 TreeMap 中插入和排序具有相同值的某些属性的不同对象，我应该改变什么？

回答by NPE

When the two weights are equal, compareTo()need to examine the names:

当两个权重相等时，compareTo()需要检查名字：

public int compareTo(Car d){
    if(this.weight>d.weight)
        return 1;
    else if(this.weight<d.weight)
        return -1;
    return this.name.compareTo(d.name);
}

This will make compareTo()consistent with equals()(the latter can now be rewritten in terms of the former). Also, the map will allow multiple entries with the same weight, provided the names differ.

这将compareTo()与equals()（后者现在可以根据前者进行重写）保持一致。此外，如果名称不同，地图将允许具有相同权重的多个条目。

回答by Jon Skeet

That is, that the object c has replaced (somewhat) object b.

也就是说，对象 c 已经替换了（在某种程度上）对象 b。

Yes, it would do. They have equal weights, so TreeMapconsiders them to be equal. A map never contains two "equal" keys (how would you look up a value?), hence one replaces the other.

是的，它会做。它们具有相同的权重，因此TreeMap认为它们是相等的。地图永远不会包含两个“相等”的键（您将如何查找值？），因此一个替换另一个。

If you don't want them to be considered equal, you need to make your compareTomethod differentiate between them (e.g. by using nameas a secondary sort order).

如果您不希望它们被视为相等，则需要使您的compareTo方法区分它们（例如，通过name用作辅助排序顺序）。

The documentation for TreeMapexplains that if your compareTomethod is not consistent with your equalsmethod (which it's not), you won't get normal Mapbehaviour:

的文档TreeMap解释说，如果您的compareTo方法与您的equals方法不一致（事实并非如此），您将无法获得正常Map行为：

Note that the ordering maintained by a tree map, like any sorted map, and whether or not an explicit comparator is provided, must be consistent with equals if this sorted map is to correctly implement the Map interface. (See Comparable or Comparator for a precise definition of consistent with equals.) This is so because the Map interface is defined in terms of the equals operation, but a sorted map performs all key comparisons using its compareTo (or compare) method, so two keys that are deemed equal by this method are, from the standpoint of the sorted map, equal. The behavior of a sorted map is well-defined even if its ordering is inconsistent with equals; it just fails to obey the general contract of the Map interface.

请注意，树映射维护的排序，就像任何排序映射一样，无论是否提供显式比较器，如果此排序映射要正确实现 Map 接口，则必须与 equals 一致。（请参阅 Comparable 或 Comparator 以获得与等于一致的精确定义。）这是因为 Map 接口是根据等于操作定义的，但排序映射使用其 compareTo（或比较）方法执行所有键比较，因此两个从排序映射的角度来看，此方法认为相等的键是相等的。排序映射的行为是明确定义的，即使它的排序与 equals 不一致；它只是不遵守 Map 接口的一般约定。

回答by Tomasz Nurkiewicz

Your compareTo()method is not consistent with equals():

您的compareTo()方法与equals()以下内容不一致：

if and only if c.compare(e1, e2)==0has the same boolean value as e1.equals(e2)for every e1and e2[...].

当且仅当c.compare(e1, e2)==0具有相同的布尔值的e1.equals(e2)每一个e1和e2[...]。

Try this instead:

试试这个：

public int compareTo(Car d){
    if(this.weight>d.weight)
        return 1;
    else if(this.weight<d.weight)
        return -1;
    else
        return this.name.compareTo(d.name);
}

In your original implementation two objects are considered equal in terms of comparator when they have the same weightbut different name, while they are different in terms of equals().

在您的原始实现中，当两个对象具有相同weight但不name同时，就比较器而言，它们被视为相等，而在equals().

回答by arcy

The Comparable interface doc says "The natural ordering for a class C is said to be consistent with equals if and only if e1.compareTo(e2) == 0 has the same boolean value as e1.equals(e2) for every e1 and e2 of class C.". But your compareTo() doesn't do that, because it doesn't check for the equality of the name field. If you put a check for that into compareTo(), it works.

Comparable 接口文档说“当且仅当 e1.compareTo(e2) == 0 对于每个 e1 和 e2 具有与 e1.equals(e2) 相同的布尔值时，才说类 C 的自然顺序与等于一致C级。”。但是您的 compareTo() 不会这样做，因为它不会检查 name 字段的相等性。如果您将其检查到 compareTo() 中，它就会起作用。