As per TreeSet two objects are shown equal but Queue shows them as unequal

Question

I have the follwing Person Class -

Person.java -

public class Person implements Comparable<Person> {
    private int id;
    private String name;

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

    public int getId() {
        return id;
    }
    public String getName() {
        return name;
    }

    @Override
    public String toString() {
        return "Person: Id = " + id + ", Name = " + name;
    }

    @Override
    public int compareTo(Person person) {
        int myReturn = 0;
        int minLength = 0;
        int i = 0;
        boolean equal = false;
        if (id > person.id) {
            myReturn = 1;
        } else if (id < person.id) {
            myReturn = -1;
        } else {
            if (name.length() > person.name.length()) {
                minLength = person.name.length();
            } else if (name.length() < person.name.length()) {
                minLength = name.length();
            } else {
                equal = true;
                minLength = name.length();
            }
            for (i = 0; i < minLength; i++) {
                if (name.charAt(i) > person.name.charAt(i))  {
                    myReturn = 1;
                    break;
                } else if (name.charAt(i) < person.name.charAt(i)) {
                    myReturn = -1;
                    break;
                } else {
                    continue;
                }
            }
            if (i == minLength) {
                if (equal) {
                    myReturn = 0;
                } else if (name.length() > person.name.length()) {
                    myReturn = 1;
                } else {
                    myReturn = -1;
                }
            }
        }
        return myReturn;
    }
}

Now, I have the following TreeClass instance -

TreeSet<Person> treeSet = new TreeSet<>(List.of(
                new Person(4, "Amrita"),
                new Person(4, "Amrita"),
                new Person(9, "Sunita"),
                new Person(12, "Nisha"),
                new Person(9, "Sunit"),
                new Person(9, "Sunitaa")
        ));

Upon printing -

Person: Id = 4, Name = Amrita
Person: Id = 9, Name = Sunit
Person: Id = 9, Name = Sunita
Person: Id = 9, Name = Sunitaa
Person: Id = 12, Name = Nisha

So clearly, the two Person instances - new Person(4, "Amrita") and new Person(4, "Amrita") are equal.

Now, I have the following Queue code. Since, Queue is a subinterface of Collection interface it implements all methods of Collection interface. So -

    Queue<Person> queue3 = new LinkedList<>(List.of(
                new Person(4, "Amrita"),
                new Person(2, "Suhana"),
                new Person(7, "Neha")
        ));
        Person person1 = new Person(4, "Amrita");
        Person person2 = new Person(9, "Sunita");
        System.out.println(queue3.contains(person1));
        System.out.println(queue3.contains(person2));

Ouput -

    false
    false

Thus it says that new Person(4, "Amrita") element of Queue and Object new Person(4, "Amrita") are unequal.

How is this possible?

Tintin · Accepted Answer · 2023-01-11T17:49:35.270

You need to override @equals and @hashCode methods in the class Person.

Explanation:

You are using TreeSet. If you don't provide an explicit Comparator while creating it, it will use natural ordering (compareTo) for sorting.
Whenever you @override compareTo(), it is highly recommended to @overide @equals.

From Collections Documentation:

It is strongly recommended (though not required) that natural orderings be consistent with equals. This is so because sorted sets (and sorted maps) without explicit comparators behave "strangely" when they are used with elements (or keys) whose natural ordering is inconsistent with equals.

To cut the long story short, since you are using TreeSet as well as other collections (List), you need to @override all three - compareTo, equals and hashCode

PS: Whenever you override @equals - please @override hashCode too. See this.

You can generate these methods inside IDE (Intellij / Eclipse/ VsCode etc) automatically. E.g. it would be something like this:

@Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Person person = (Person) o;
        return id == person.id && Objects.equals(name, person.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(id, name);
    }

@Payel, I edited and added some example code.. Regarding hash-code, I included a link, which would explain. — Tintin, May 25 '22 at 15:11

score 1 · Answer 2 · answered May 25 '22 at 15:09

TreeSet exclusively uses the comparator to determine equality. Any 2 entries such that comparator.compare(a, b) returns 0 are deemed equal. Neither equals nor hashCode are invoked at all.

Most other collections exclusively use either just equals, or a combination of equals and hashCode to determine this.

Thus, if you write a class whose equals, hashCode, and compare methods are in disagreement, you can create the situation you described: Where TreeSet considers them equal but e.g. HashSet does not.

The solution is to properly apply the rules as laid out in the javadocs of the various java.util classes:

a.equals(b)? Then, b.equals(a) must also hold, regardless of the types.
a.equals(a) must be true.
a.equals(anything) cannot throw any exceptions, except the forced NPE if a is null. Same for a.hashCode().
a.equals(null) must be false.
a.equals(b) and b.equals(c)? Then a.equals(c) must also be true.
a.equals(b)? Then a.hashCode() == b.hashCode() must also be true. The reverse does not hold (equal hashcodes? That doesn't imply equal objects).
a.compare(b) is below 0? Then b.compare(a) must be above 0.
a.compare(a) must be 0.
a.compare(b) == 0 must match with a.equals(b) If one is true the other must be true and vice versa.
a.compare(b) < 0 and b.compare(c) < 0? Then a.compare(c) must also be below 0. Same for above 0.
Unlike equals and hashCode, compare is allowed to throw a number of exceptions.

It's a lot of rules. They are easy to understand (bordering on the obvious), and yet they are quite hard to properly apply especially if you involve the idea that java has a type hierarchy.

Trivial example:

ArrayList has an equals impl that will check if the provided object is a list of any kind, and if it is, it'll just do an elem-by-elem comparison.

This means you CANNOT write a class that implements List and add equality-affecting properties of ANY sort, period.

For example, this class:

class ColouredList<T> extends ArrayList<T> {
  private Color color;

  public ColouredList(Color color) {
    this.color = color;
  }

  // and so on
}

CANNOT BE WRITTEN - unless you disregard colour entirely, and e.g. an empty blue list is deemed equal to an empty red one. Because emptyPlainArrayList.equals(blueEmptyList) is true and you can't make that false (as you do not control the equals impl of ArrayList), and so is emptyPlainArrayList.equals(redEmptyList), therefore, blueEmptyList.equals(redEmptyList) also has to be true.

This rule is a logical consequence of the ruleset, and yet, not obvious and in fact a somewhat common mistake to think you can do that.

Hence, easy, almost obvious rules that combine to make a system that is much more complex than you'd think.

You violated one of the rules here; given what you pasted, seems like a simple one: You added a natural comparison order to your class but failed to implement hashCode and equals. You must implement these methods, in order to follow the rule that a.equals(b) and a.compare(b) == 0 have to hold (and you have to implement hashCode to follow the rule "if a.equals(b) then you have to ensure a.hashCode() == b.hashCode().

I suggest Project Lombok or your IDE's "generate equals and hashcode" option. These methods, too, can be a bit tricky to write properly.

As per TreeSet two objects are shown equal but Queue shows them as unequal

2 Answers2