Using Comparable to compare objects and sorting them in a TreeMap

Question

II cannot understand how should the natural ordering of class be "consistent with equals" when implementing the Comparable interface. 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:

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:

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?

Solution 1

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

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.

Solution 2

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

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

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

The documentation for TreeMap explains that if your compareTo method is not consistent with your equals method (which it's not), you won't get normal Map behaviour:

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.

Solution 3

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

if and only if c.compare(e1, e2)==0 has the same boolean value as e1.equals(e2) for every e1 and 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 weight but different name, while they are different in terms of equals().