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

Question

From the JavaDoc of TreeMap :

Note that the ordering maintained by a sorted map (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 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.

Can some one give an concrete example to demonsrate the problem that might occur if ordering is not consistent with equals ? Take for example User defined class that has a natural ordering i.e it implements Comparable . Also do all internal classes in JDK maintain this invariant?

Answer 1

Here's a simple but realistic example of what can happen if a comparison method is inconsistent with equals. In the JDK, BigDecimal implements Comparable but its comparison method is inconsistent 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 the comparison method of BigDecimal considers only the numeric value, but equals also considers the precision. Since 0.0 and 0.00 have different precisions, they are unequal even though they have the same numeric value. (For an explanation, see this answer.)

Here's an example of what it means for a TreeSet to violate the general contract of Set. (It's the same situation with TreeMap and Map but it's a bit easier to demonstrate using sets.) Let's compare the results of contains to the result of getting the element out of 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 here is that the TreeSet says it contains the object zz, but it's unequal to the element that's actually contained in the set. The reason is that TreeSet uses its comparison method (BigDecimal.compareTo) to determine set membership, not equals.

Now let's 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 sets that are equal, but one set says that it contains an object but another set says that it doesn't contain the same object. Again, this reflects the fact that TreeSet is using the comparison method whereas HashSet is using equals.

Now let's add 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 that's weird. One set says it's equal to the other, but the other set says it's not equal to the first! To understand this, you need to understand how equality of sets is determined. Two sets are considered equal if a) they are of the same size, and b) each element in the other set is also contained in this set. That is, if you have

set1.equals(set2)

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

ts.equals(hs2)

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

Now when we do

hs2.equals(ts)

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

Answer 2

Say we have this simple Student class implementing Comparable<Student> but not overriding equals()/hashCode(). Of course equals() is not consistent with compareTo() - two different students 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 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 are nicely sorted according to their age (despite being inserted in different order) and fetching student using new Student(22) key works as well and returns "twenty two". This means we can safely use Student class in TreeMap.

However change students to HashMap and things go bad:

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

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

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

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

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