CODEWITHSUNDEEP
javaequalscomparetotreeset
ruchun huang
ruchun huang

Reputation: 53

TreeSet doesn't work, what's wrong with the following code?

The following code should print 3 persons, but it actually print 4 persons, why? Person("a", 1) and Person("a", 4) should be treated as the same, but they are not.

import java.util.TreeSet;
public class Person implements Comparable<Person>{
    public Person(String name, int age){
        this.name = name;
        this.age = age;
    }
    public String name;
    public int age;

    @Override
    public int compareTo(Person o) {
        if(this.name.equals(o.name)){
            return 0;
        }else if(this.age <= o.age){
            return -1;
        }else {
            return 1;
        }
    }
    @Override public boolean equals(Object other) {
        return name.equals(((Person)other).name);
    }

    @Override public int hashCode() {
        return age * 31; 
    }
    public static void main(String[] args) {
        TreeSet<Person> persons = new TreeSet<Person>();
        persons.add(new Person("a", 1));
        persons.add(new Person("b", 3));
        persons.add(new Person("c", 2));
        persons.add(new Person("a", 4));//This should be ignored.

        /*Here should print the first 3 persons, but it prints 4 persons*/
        for(Person h: persons){
            System.out.println(h.name + ":" +h.age);
        }
    }
}

Result:
a:1
c:2
b:3
a:4

Upvotes: 4

Views: 451

Answers (4)

Malt
Malt

Reputation: 30335

The problem is the compareTo method, which performs comparisons based on age, but determines equality based on the Person's name, making it inconsistent with itself.

After inserting the first 3 Persons, the tree looks something like this (forgive the poor ASCII art):

    (c,2)
      |
     /\
 (a,1) (b,3)

Then (a,4) is inserted, it's compared to (c,2) based on the age. The age (4) is bigger than (2), so we go to the right. The next comparison is with (b,3). (a,4) is again bigger, so it's added as a new node to the tree (since there's nothing else to compare to). If instead of adding (a,4) you'd add (a,0), then there would be a comparison with (a,1), and the result would be:

a:1
c:2
b:3

Upvotes: 4

JB Nizet
JB Nizet

Reputation: 692181

Your compareTo method doesn't respect the contract of Comparable.compareTo().

It should be symmetric: if a < b, then b > a. That is not the case since if a and b have the same name and the same age, a.compareTo(b) is -1, and b.compareTo(a) is -1 as well. So a is bigger than b and smaller than b at the same time.

It should be transitive: if a < b and b < c, then a < c. This is not the case:

  • (a, 3) < (b, 7),
  • (b, 7) < (a, 10)
  • but (a, 3) = (a, 10)

Given that the contract is not respected, you can't expect anything from TreeSet, which assumes that the contract is respected to work.

Upvotes: 3

Sotirios Delimanolis
Sotirios Delimanolis

Reputation: 280179

A TreeSet is implemented with a TreeMap which is a red black tree. When you add the first element, it becomes root

(A, 1)

When you add the second, it has a differdnt name and a bigger age, so it becomes the root's right child.

(A, 1)
    \
    (B, 2)

When you add the third, it's again bigger than those. The tree reorganizes itself for balance.

    (B, 2)
    /    \
(A, 1)  (C, 3)

You then add your final element. 4 is bigger than 2, so search goes down the right branch and doesn't find an element with name "a", so it adds a new entry.

    (B, 2)
    /    \
(A, 1)  (C, 3)
            \ 
            (A, 4)

Upvotes: 3

Ray
Ray

Reputation: 3201

Your implementation of compareTo doesn't match your implementation of equals. TreeSet operates on compareTo.

As a side note: The implementation of hashCode() is also wrong, as it's not in line with equals either.

Upvotes: 1

Related Questions