23

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?

Gunnar Bernstein
  • 6,074
  • 2
  • 45
  • 67
Alpedar
  • 1,314
  • 1
  • 8
  • 12
  • 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. – James P. Aug 29 '11 at 12:27
  • Hash set is not sorted. I inculuded it in example to show results not affected by comparator. – Alpedar Aug 29 '11 at 12:42
  • 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. – James P. Aug 29 '11 at 13:12
  • 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: http://ifw2.sourceforge.net/apidocs/ifw2/net/infordata/ifw2/util/CompositeComparator.html – James P. Aug 29 '11 at 13:16
  • @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 ? – tusharRawat Dec 28 '20 at 08:37
  • @tusharRawat 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 – Alpedar Dec 29 '20 at 12:37
  • @Alpedar, so basically we need our own implementation of Red-Black Tree, instead of using TreeSet present in the Collections API ? – tusharRawat Dec 29 '20 at 15:44
  • @tusharRawat 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. – Alpedar Jan 05 '21 at 15:34

6 Answers6

22

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."

Lukas Eder
  • 211,314
  • 129
  • 689
  • 1,509
  • 7
    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. – supercat Jun 16 '13 at 17:00
  • 1
    @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` – Lukas Eder Jun 17 '13 at 07:38
  • 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`. – supercat Jun 17 '13 at 15:03
  • 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... – supercat Jun 17 '13 at 15:12
  • ..."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. – supercat Jun 17 '13 at 15:16
  • @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 ? – tusharRawat Dec 28 '20 at 13:45
  • @tusharRawat: I suggest asking a new question – Lukas Eder Dec 30 '20 at 09:48
10

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)

nfechner
  • 17,295
  • 7
  • 45
  • 64
7

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?

Jon Skeet
  • 1,421,763
  • 867
  • 9,128
  • 9,194
  • 1
    "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. – James P. Aug 29 '11 at 12:53
  • 1
    @James: It can be reasonably arbitrary, so long as it produces a total ordering which is still consistent with the original primary ordering. – Jon Skeet Aug 29 '11 at 12:54
  • @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 ? – tusharRawat Dec 28 '20 at 13:46
  • @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. – Jon Skeet Dec 28 '20 at 14:35
2

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)

ratchet freak
  • 47,288
  • 5
  • 68
  • 106
1

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 )

OscarRyz
  • 196,001
  • 113
  • 385
  • 569
0

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.

S.L. Barth is on codidact.com
  • 8,198
  • 71
  • 51
  • 66