[ACCEPTED]-What does comparison being consistent with equals mean ? What can possibly happen if my class doesn't follow this principle?-comparable

Here's a simple but realistic example of 48 what can happen if a comparison method is 47 inconsistent with equals. In the JDK, BigDecimal implements 46 Comparable but its comparison method is inconsistent 45 with equals. For example:

> BigDecimal z = new BigDecimal("0.0")
> BigDecimal zz = new BigDecimal("0.00")
> z.compareTo(zz)
0
> z.equals(zz)
false

This is because 44 the comparison method of BigDecimal considers only 43 the numeric value, but equals also considers the 42 precision. Since 0.0 and 0.00 have different precisions, they 41 are unequal even though they have the same 40 numeric value.

Here's an example of what 39 it means for a TreeSet to violate the general contract 38 of Set. (It's the same situation with TreeMap and 37 Map but it's a bit easier to demonstrate using 36 sets.) Let's compare the results of contains to 35 the result of getting the element out of 34 the set and calling equals:

> TreeSet<BigDecimal> ts = new TreeSet<>()
> ts.add(z)
> ts.contains(z)
true
> z.equals(ts.iterator().next())
true
> ts.contains(zz)
true
> zz.equals(ts.iterator().next())
false

The surprising thing 33 here is that the TreeSet says it contains the object 32 zz, but it's unequal to the element that's 31 actually contained in the set. The reason 30 is that TreeSet uses its comparison method (BigDecimal.compareTo) to 29 determine set membership, not equals.

Now let's 28 compare TreeSet to HashSet:

> HashSet<BigDecimal> hs = new HashSet<>(ts)
> hs.equals(ts)
true
> ts.contains(zz)
true
> hs.contains(zz)
false

This is strange. We have two 27 sets that are equal, but one set says that 26 it contains an object but another set says 25 that it doesn't contain the same object. Again, this 24 reflects the fact that TreeSet is using the comparison 23 method whereas HashSet is using equals.

Now let's add 22 the other object to a HashSet and see what happens:

> HashSet<BigDecimal> hs2 = new HashSet<>()
> hs2.add(zz)
> ts.equals(hs2)
true
> hs2.equals(ts)
false

Now 21 that's weird. One set says it's equal to 20 the other, but the other set says it's not 19 equal to the first! To understand this, you 18 need to understand how equality of sets 17 is determined. Two sets are considered equal 16 if a) they are of the same size, and b) each 15 element in the other set is also contained 14 in this set. That is, if you have

set1.equals(set2)

then the 13 equality algorithm looks at the sizes and 12 then it iterates over set2, and for each 11 element it checks whether that element is 10 contained in set1. That's where the asymmetry 9 comes in. When we do

ts.equals(hs2)

both sets are of size 8 1, so we proceed to the iteration step. We 7 iterate over hs2 and use then call the TreeSet.contains method 6 -- which uses the comparison method. As far as the TreeSet is concerned, it's equal 5 to the HashSet hs2.

Now when we do

hs2.equals(ts)

the comparison 4 goes the other way. We iterate over the 3 TreeSet and get its element, and ask hs2 whether it 2 contains that element. Since the HashSet.contains uses equals, it returns 1 false, and the overall result is false.

Say we have this simple Student class implementing 24 Comparable<Student> but not overriding equals()/hashCode(). Of course equals() is not 23 consistent with compareTo() - two different students 22 with the same age aren't equal:

class Student implements Comparable<Student> {

    private final int age;

    Student(int age) {
        this.age = age;
    }

    @Override
    public int compareTo(Student o) {
        return this.age - o.age;
    }

    @Override
    public String toString() {
        return "Student(" + age + ")";
    }
}

We can safely 21 use it in TreeMap<Student, String>:

Map<Student, String> students = new TreeMap<Student, String>();
students.put(new Student(25), "twenty five");
students.put(new Student(22), "twenty two");
students.put(new Student(26), "twenty six");
for (Map.Entry<Student, String> entry : students.entrySet()) {
    System.out.println(entry);
}
System.out.println(students.get(new Student(22)));

The results are easy to predict: students 20 are nicely sorted according to their age 19 (despite being inserted in different order) and 18 fetching student using new Student(22) key works as well 17 and returns "twenty two". This means we can safely use 16 Student class in TreeMap.

However change students to HashMap and things 15 go bad:

Map<Student, String> students = new HashMap<Student, String>();

Obviously the enumeration of items 14 returns "random" order due to 13 hashing - that's fine, it doesn't violate 12 any Map contract. But the last statement is 11 completely broken. Because HashMap uses equals()/hashCode() to compare 10 instances, fetching value by new Student(22) key fails 9 and returns null!

This is what the JavaDoc tries 8 to explain: such classes will work with 7 TreeMap but might fail to work with other Map implementations. Note 6 that Map operations are documented and defined 5 in terms of equals()/hashCode(), e.g. containsKey():

[...] returns true 4 if and only if this map contains a mapping 3 for a key k such that (key==null ? k==null : key.equals(k))

Thus I don't believe 2 there are any standard JDK classes that 1 implemente Comparable but fail to implement equals()/hashCode() pair.

The contract of the Comparable interface allows for non-consistent behaviour:

It 8 is strongly recommended (though not required) that 7 natural orderings be consistent with equals.

So 6 in theory, it is possible that a class in 5 the JDK had a compareTo not consistent with equals. One 4 good example is BigDecimal.

Below is a contrived example 3 of a comparator that is not consistent with 2 equals (it basically says that all strings 1 are equal).

Output:

size: 1
content: {a=b}

public static void main(String[] args) {
    Map<String, String> brokenMap = new TreeMap<String, String> (new Comparator<String>() {

        @Override
        public int compare(String o1, String o2) {
            return 0;
        }
    });

    brokenMap.put("a", "a");
    brokenMap.put("b", "b");
    System.out.println("size: " + brokenMap.size());
    System.out.println("content: " + brokenMap);
}

Here is another example of when consistency 28 with equals AND total ordering are important 27 to implement.

Say we have an object MyObject which 26 has two fields: id and quantity. id as its name suggests 25 is the natural key of the object and quantity is 24 just an attribute.

public class MyObject {
  int id;
  int quantity;
  ...
}

Let's imagine that we 23 want to use a collections of MyObject sorted by 22 quantity descending. The First comparator we can 21 write is:

Comparator<MyObject> naiveComp = new Comparator<MyObject>() {
  @Override
  public int compare(MyObject o1, MyObject o2) {
    return o2.quantity - o1.quantity;
  }
};

Using MyObject instances equipped with 20 this comparator in a TreeMap/TreeSet fails 19 because it comparator is not consistent with equals (see full 18 code below). Let's make it consistent with 17 equals:

Comparator<MyObject> slightlyBetterComp = new Comparator<MyObject>() {
  @Override
  public int compare(MyObject o1, MyObject o2) {
    if (o1.equals(o2)) {
      return 0;
    }
    if (o1.quantity == o2.quantity) {
      return -1; // never 0
    }
    return o2.quantity - o1.quantity; // never 0
  }
};

However, this fails again to fit 16 in TreeSet/TreeMap! (see full code below) This 15 is because the ordering relation is not 14 total, i.e. not any two objects can be strictly 13 put in an ordering relationship. In this 12 comparator, when quantity fields are equal, the 11 resulting ordering is undetermined.

A better 10 comparator would be:

Comparator<MyObject> betterComp = new Comparator<MyObject>() {
  @Override
  public int compare(MyObject o1, MyObject o2) {
    if (o1.equals(o2)) {
      return 0;
    }
    if (o1.quantity == o2.quantity) {
      return o1.id - o2.id; // never 0
    }
    return o2.quantity - o1.quantity; // never 0
  }
};

This comparator ensures 9 that:

• when compareTo returns 0 it implies that two objects are equal (initial check for equality)
• all items are totally ordered by using id as a discriminant ordering field when quantity are equal

Full Testing Code:

package treemap;

import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;

public class MyObject {
  int id;
  int quantity;

  public MyObject(int id, int quantity) {
    this.id = id;
    this.quantity = quantity;
  }

  @Override
  public int hashCode() {
    int hash = 7;
    hash = 97 * hash + this.id;
    return hash;
  }

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

  @Override
  public String toString() {
    return "{" + id + ", " + quantity + "}";
  }

  public static void main(String[] args) {
    String format = "%30.30s: %s\n";
    Map<MyObject, Object> map = new HashMap();
    map.put(new MyObject(1, 100), 0);
    map.put(new MyObject(2, 100), 0);
    map.put(new MyObject(3, 200), 0);
    map.put(new MyObject(4, 100), 0);
    map.put(new MyObject(5, 500), 0);
    System.out.printf(format, "Random Order", map.keySet());

    // Naive non-consisten-with-equal and non-total comparator
    Comparator<MyObject> naiveComp = new Comparator<MyObject>() {
      @Override
      public int compare(MyObject o1, MyObject o2) {
        return o2.quantity - o1.quantity;
      }
    };
    Map<MyObject, Object> badMap = new TreeMap(naiveComp);
    badMap.putAll(map);
    System.out.printf(format, "Non Consistent and Non Total", badMap.keySet());

    // Better consisten-with-equal but non-total comparator
    Comparator<MyObject> slightlyBetterComp = new Comparator<MyObject>() {
      @Override
      public int compare(MyObject o1, MyObject o2) {
        if (o1.equals(o2)) {
          return 0;
        }
        if (o1.quantity == o2.quantity) {
          return -1; // never 0
        }
        return o2.quantity - o1.quantity; // never 0
      }
    };
    Map<MyObject, Object> slightlyBetterMap = new TreeMap(naiveComp);
    slightlyBetterMap.putAll(map);
    System.out.printf(format, "Non Consistent but Total", slightlyBetterMap.keySet());

    // Consistent with equal AND total comparator
    Comparator<MyObject> betterComp = new Comparator<MyObject>() {
      @Override
      public int compare(MyObject o1, MyObject o2) {
        if (o1.equals(o2)) {
          return 0;
        }
        if (o1.quantity == o2.quantity) {
          return o1.id - o2.id; // never 0
        }
        return o2.quantity - o1.quantity; // never 0
      }
    };
    Map<MyObject, Object> betterMap = new TreeMap(betterComp);
    betterMap.putAll(map);
    System.out.printf(format, "Consistent and Total", betterMap.keySet());
  }
}

Output:

                  Random Order: [{5, 500}, {4, 100}, {3, 200}, {2, 100}, {1, 100}]
  Non Consistent and Non Total: [{5, 500}, {3, 200}, {4, 100}]
      Consistent but Not Total: [{5, 500}, {3, 200}, {4, 100}]
          Consistent and Total: [{5, 500}, {3, 200}, {1, 100}, {2, 100}, {4, 100}]

Conclusion:

Although 8 I think it is very legitimate to segregate 7 identity from ordering conceptually. For 6 instance, in relational database terms:

select * from MyObjects order by quantity

works 5 perfectly. We don't care about object identity 4 here, nor we want total ordering

However, due 3 to constraints in tree based collections 2 implementation, one has to ensure that any 1 comparator they write:

• is consistency with equals
• provide a total ordering over all possible objects