Understanding TreeSet when compareto returns 0

Question

I have created a Student class like this:

public class Student implements Comparable<Student> {

    private String firstName;
    private String lastName;

    public Student(String firstName, String lastName) {
        this.firstName = firstName;
        this.lastName = lastName;
    }

    // Getters & Setters follow here...

    @Override
    public int compareTo(Student student) {
        int hash = this.firstName.compareTo(student.firstName);
        return hash;
    }

    @Override
    public String toString() {
        return "Student [firstName=" + firstName + ", lastName=" + lastName
                + "]";
    }

}

This is my test class where I just add elements to my TreeSet:

public class SortedSetExample1 {
    public static void main(String[] args) {
        SortedSet<Student> set = new TreeSet<Student>();
        set.add(new Student("A1","A2"));
        set.add(new Student("B1","B2"));
        set.add(new Student("A1","B2"));
        set.add(new Student("A2","B2"));
        System.out.println(set);
    }
}

As per my program the output is:

[Student [firstName=A1, lastName=A2], Student [firstName=A2, lastName=B2], Student [firstName=B1, lastName=B2]]

In my test class I am adding Student objects to TreeSet, and also I have not overridden the hashCode & equals methods. So I was expecting that the TreeSet will hold all the 4 objects but I can also see that it contains 3 objects. Can you please explain why new Student("A1","B2") is not part of my TreeSet?

Also as per the Java docs for TreeSet here, it says:

Adds the specified element to this set if it is not already present. More formally, adds the specified element e to this set if the set contains no element e2 such that (e==null ? e2==null : e.equals(e2)). If this set already contains the element, the call leaves the set unchanged and returns false.

As I have not overridden the equals method then why the collection is not having all the four elements?

Solution 1

As java.util.TreeSet says:

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

Kudos to @Jon Skeet.

Solution 2

Since you have compared only first name in compareTo method, you need

 @Override
public int compareTo(Student student) {
    int comp = this.firstName.compareTo(student.firstName);
    if(comp==0) return this.lastName.compareTo(student.lastName);
    return comp;
}

when compareTo returns 0, treeSet assumes that its duplicate.

Solution 3

Although question is quite old, but here is one very important point to understand which most people ignores while implementation.

TreeSet does not compare the new element with all the existing elements in the Set. It uses binary search technique. Therefore, If your input element is equal to an existing element (as per compareTo contract) and same lies on the left side of tree and your compareTo method is implemented such a way that it forces your new element to lie on right side of tree, your TreeSet will not reject the new element even though same element is present inside it already (as per compareTo contract). Lets see the following simple example.

I need to sort Items having properties as key and priority.

package com.manish;
import java.util.TreeSet;
public class Main {
    static class Item implements Comparable<Item> {
        private long key;
        private int priority;
        public Item(long key, int priority) {
            super();
            this.key = key;
            this.priority = priority;
        }

        /*
         * Items should be treated equal if Keys are equal.
         * Higher priority item should be treated as greater item.
         * If priorities are same, lower key value item should be
         * treated as greater item.
         */
        @Override
        public int compareTo(Item o) {
            if (this.key == o.key) {
                return 0;
            }
            if (this.priority != o.priority) {
                return this.priority - o.priority;
            } else {
                return this.key < o.key ? 1 : -1;
            }
        }
        @Override
        public String toString() {
            return "Item [key=" + key + ", priority=" + priority + "]";
        }
    }
    public static void main(String[] args) {
        TreeSet<Item> set = new TreeSet<>();
        set.add(new Item(2, 1));
        set.add(new Item(4, 3));
        set.add(new Item(3, 1)); //line 1
        set.add(new Item(3, 2)); //line 2. Same item as Item(3,1)
        while (!set.isEmpty())
            System.out.println(set.pollFirst());
    }
}

Output:

Item [key=3, priority=1]
Item [key=2, priority=1]
Item [key=3, priority=2]
Item [key=4, priority=3]

However, if you swap the line 1 and line 2 code, the output will get changed as below.

Item [key=2, priority=1]
Item [key=3, priority=2]
Item [key=4, priority=3]

Solution 4

That is because TreeSet uses compareTo (or Comparator.compare) to test whether two elements are equal. This is what the docs say about it.

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.

View more solutions

Comments

[almightyGOSU]

I think it is because of your compareTo()..

[learner]

@Gosu, the compareTo just compares based on firstName but why I am not allowed to add 2 objects having same firstName but different lastNames?

[meskobalazs]

possible duplicate of Java, Why it is implied that objects are equal if compareTo() returns 0?

[Ed J]

While the summary referenced here has the information, the documentation for TreeSet.add() is unfortunately incorrect, as it makes no mention of compareTo. Just to be certain, I wrote a unit test that proves it. "Adds the specified element to this set if it is not already present. More formally, adds the specified element e to this set if the set contains no element e2 such that (e==null ? e2==null : e.equals(e2)). If this set already contains the element, the call leaves the set unchanged and returns false." docs.oracle.com/javase/7/docs/api/java/util/TreeSet.html#add‌​(E)

[Manish Bansal]

One important point missing here is that TreeSet does not perform comparison with all the elements. Since, the TreeSet is a sorted Set, It uses binary search technique. And this could lead to unique issues. Check my answer for example.