Why it is implied that objects are equal if compareTo() returns 0?

Question

Let's have a class Person. Person has a name and height.

Equals and hashCode() takes into account only name. Person is comparable (or we implement comparator for it, does not matter which one). Persons are compared by height.

It seems reasonable to expect a situation where two different persons can have same height, but e.g. TreeSet behaves like compareTo()==0 means equals, not merely same size.

To avoid this, comparison can secondarily look at something else if size is the same, but then it cannot be used to detect same sized different objects.

Example:

import java.util.Comparator;
import java.util.HashSet;
import java.util.Objects;
import java.util.Set;
import java.util.TreeSet;

public class Person implements Comparable<Person> {

private final String name;
private int height;

public Person(String name,
        int height) {
    this.name = name;
    this.height = height;
}

public int getHeight() {
    return height;
}

public void setHeight(int height) {
    this.height = height;
}

public String getName() {
    return name;
}

@Override
public int compareTo(Person o) {
    return Integer.compare(height, o.height);
}

public boolean equals(Object obj) {
    if (obj == null) {
        return false;
    }
    if (getClass() != obj.getClass()) {
        return false;
    }
    final Person other = (Person) obj;
    if (!Objects.equals(this.name, other.name)) {
        return false;
    }
    return true;
}

public int hashCode() {
    int hash = 5;
    hash = 13 * hash + Objects.hashCode(this.name);
    return hash;
}

public String toString() {
    return "Person{" + name + ", height = " + height + '}';
}

public static class PComparator1 implements Comparator<Person> {

    @Override
    public int compare(Person o1,
            Person o2) {
        return o1.compareTo(o2);
    }
}

public static class PComparator2 implements Comparator<Person> {

    @Override
    public int compare(Person o1,
            Person o2) {
        int r = Integer.compare(o1.height, o2.height);
        return r == 0 ? o1.name.compareTo(o2.name) : r;
    }
}

public static void test(Set<Person> ps) {
    ps.add(new Person("Ann", 150));
    ps.add(new Person("Jane", 150));
    ps.add(new Person("John", 180));
    System.out.println(ps.getClass().getName());
    for (Person p : ps) {
        System.out.println(" " + p);
    }
}

public static void main(String[] args) {
    test(new HashSet<Person>());
    test(new TreeSet<Person>());
    test(new TreeSet<>(new PComparator1()));
    test(new TreeSet<>(new PComparator2()));
}
}

result:

java.util.HashSet
 Person{Ann, height = 150}
 Person{John, height = 180}
 Person{Jane, height = 150}

java.util.TreeSet
 Person{Ann, height = 150}
 Person{John, height = 180}

java.util.TreeSet
 Person{Ann, height = 150}
 Person{John, height = 180}

java.util.TreeSet
 Person{Ann, height = 150}
 Person{Jane, height = 150}
 Person{John, height = 180}

Do you have idea why it is so?

Jorge

There probably isn't a reason. It comes accross a simplified mathematical convention that equal objects give a return of 0 with compareTo. What criteria are used is left to the creator of the class. It seems you're asking another question here with respect to TreeSets though. Could you clarify please? P.S: I think HashSet isn't sorted. – Paresis

Hash set is not sorted. I inculuded it in example to show results not affected by comparator. – Jorge

Ok, I see what you're getting at. In the two TreeSets of the middle Jane has disappeared most likely because of compareTo or equals. This figures as Sets only retain unique elements. As suggested below, I'd use more attributes in the compareTo of your Person class as relevant or use a separate Comparator class depending on the context (as you've done with PComparator2). Alternatively, you could define a series of internal Comparators (NameComparator,HeightComparator,EyeColorComparator...) to use exclusively with your Person class. – Paresis

In passing, I don't know if it's possible to combine Comparators. If not possible, you could write a composite pattern like this one: ifw2.sourceforge.net/apidocs/ifw2/net/infordata/ifw2/util/… – Paresis

@Alpedar, If we do updates such as ps.add(new Person("Ann", 200)), then this is going to create a new entry in TreeSet instead of updating the height of Person named "Ann". Is there a way we can achieve updates in this custom implementation of PComparator2 for a TreeSet<Person> ? – Fawnfawna

@Fawnfawna remove old and add new. To achieve real update, you would need custom data structure (some kind of heap) where you would have direct access to node where person is stored and then you can update it and bublle up or down – Jorge

@Alpedar, so basically we need our own implementation of Red-Black Tree, instead of using TreeSet present in the Collections API ? – Fawnfawna

@Fawnfawna depends on your needs. I'have seen some navigation software (in C++, but api had same weakness) to use workarounds like remove&reinsert or mark data as stale and insert new value and when you dequeue "stale" you do nothhing with it and continue to next. But to achieve maximum efficiency you need to use something outside standard java library. – Jorge

Answer 1

Extract from the java.util.SortedSet javadoc:

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

Hence, in other words, SortedSet breaks (or "extends") the general contracts for Object.equals() and Comparable.compareTo. See the contract for compareTo:

It is strongly recommended, but not strictly required that (x.compareTo(y)==0) == (x.equals(y)). Generally speaking, any class that implements the Comparable interface and violates this condition should clearly indicate this fact. The recommended language is "Note: this class has a natural ordering that is inconsistent with equals."

Euphonize

I would not consider it reasonable for two objects which report themselves as equals did not also report a compareTo of zero, but would not consider it unreasonable for two objects to be unranked and yet distinct; IMHO, a well-written sorted set implementation should be prepared for such a possibility. – Foulness

@supercat: Yes, java.math.BigDecimal is such a type. 1.0 and 1.00 are "unranked", yet "distinct". Nonetheless, given the SortedSet contract, the two values are considered "equal" by SortedSet, unlike Set – Euphonize

Having a SortedSet find method regard as a match anything where compareTo yields zero would be reasonable behavior. Having it test all the items where compareTo yields zero and look for one where equals returns true would also be reasonable, and may be more useful in some cases. My point was that it would be bad to e.g. use binary search to identify a single location where an item was expected to be and then say the item wasn't in the collection if that single location didn't report equals while ignoring the possibility of a nearby item reporting equals. – Foulness

In any case, I like your example. It brings up another point, which is that it's often sensible for objects which encapsulate numbers to have more than one concept of equality and ranking. In some cases, having 1.0 and 1.00 rank as equal may be better; in other cases, it would be better to have all recognizably-distinct values ranked separately. Further, with floating-point numbers, the concepts of "X and Y are not discernibly different" and "X and Y seem to represent the same value" are not equivalent; it's possible that a more accurate statement would be... – Foulness

..."X and Y are indistinguishable, but neither has enough precision to meaningfully say whether they represent the same number [e.g. both are +INF, or both are NaN]". The latter style of test wouldn't be usable in a collection (since it's not an equivalence relation), but could be useful in many algorithms. It's too bad there's no clean-looking syntax to set the "default" rules within a block of code. – Foulness

@LukasEder , If we do updates such as ps.add(new Person("Ann", 200)), then this is going to create a new entry in TreeSet instead of updating the height of Person named "Ann". Is there a way we can achieve updates in this custom implementation of PComparator2 for a TreeSet<Person> ? – Fawnfawna

@tusharRawat: I suggest asking a new question – Euphonize

Answer 2

It is recommended that compareTo only returns 0, if a call to equals on the same objects would return true:

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. Note that null is not an instance of any class, and e.compareTo(null) should throw a NullPointerException even though e.equals(null) returns false.

(From the JDK 1.6 Javadocs)

Mentholated

It is strongly recommended, but not strictly required, according to the Comparable Javadoc – Euphonize

Answer 3

TreeSet doesn't operate using hash codes and equality - it only operates on the basis of the comparator you give it. Note that the Javadoc states:

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

In your case, your comparison *isn't consistent with equals, so your set doesn't obey the general contract of Set.

Why not just add more aspects to the comparison so that only equal elements compare with a result of 0?

Bayles

"Why not just add more aspects to the comparison so that only equal elements compare with a result of 0?" This would be the most logical approach. However, when does this turn into a comparison between Apples and Oranges? Would it be really meaningful to say that Tom at 1m70 is considered as < with respect to Sarah at 1m70. A subjective question, I know, but I felt I should ask. P.S: I'm guessing this is where a separate Comparator comes in useful. – Paresis

@James: It can be reasonably arbitrary, so long as it produces a total ordering which is still consistent with the original primary ordering. – Bayles

@JonSkeet , If we do updates such as ps.add(new Person("Ann", 200)), then this is going to create a new entry in TreeSet instead of updating the height of Person named "Ann". Is there a way we can achieve updates in this custom implementation of PComparator2 for a TreeSet<Person> ? – Fawnfawna

@tusharRawat: It would be better to ask a new question (with your own research) instead of adding a comment to an answer from 9 years ago. – Bayles

Answer 4

you can fix it by using name for another comparison when the heights are equal

@Override
public int compareTo(Person o) {
    if(height == o.height)return name.compareTo(o.name);

    return Integer.compare(height, o.height);
}

since names are unique this will only return 0 if this.equals(o)

Myrlmyrle

Answer 5

It is strongly recommended, but not strictly required that (x.compareTo(y)==0) == (x.equals(y)) [1]

So it's fine that you compare with a different criteria than the used on equals granted that you document it.

However it would be better if your compare by the same criteria and if needed provide a custom comparator which works on the new criteria ( height in the case of Person )

Pipette

Answer 6

When you give Person a Comparator that compares instances on the height attribute of the Person, it really means that two Person instances are the same if they have the same height. You will have to make a Comparator that is specific for class Person.

Petrapetracca