CODEWITHSUNDEEP
javatreeset
Joker
Joker

Reputation: 11146

Equal elements and Tree set

Created a static nested class which implements Comparable, and override Object.equals such that e1.compareTo(e2)==0 and e1.equals(e2)==true are not synonymous.

Then i add the objects into TreeSet and HashSet respectively using its add method.

I expected that insertion of multiple such objects into either a TreeSet or a HashSet will succeed, since both claim reliance on equals to determine uniqueness but i found inserting multiple such objects into a TreeSet will fail while inserting them into a HashSet will succeed.

public class Test {

    /*
     * This inner class deliberately has a compareTo method that is not
     * consistent with equals
     */
    static class TestObject implements Comparable<TestObject> {
        @Override
        public int compareTo(TestObject arg0) {
            // No two of these objects can be ordered
            return 0;
        }

        @Override
        public boolean equals(Object arg0) {
            // No two of these objects are ever equal to each other
            return false;
        }
    }

    public static void printSuccess(boolean success) {
        if (success)
            System.out.println(" Success");
        else
            System.out.println(" Failure");
    }

    public static void main(String[] args) {
        TreeSet<TestObject> testTreeSet = new TreeSet<TestObject>();
        HashSet<TestObject> testHashSet = new HashSet<TestObject>();

        System.out.println("Adding to the HashSet:");
        printSuccess(testHashSet.add(new TestObject()));
        printSuccess(testHashSet.add(new TestObject()));
        printSuccess(testHashSet.add(new TestObject()));

        System.out.println("Copying to the TreeSet:");
        for (TestObject to : testHashSet) {
            printSuccess(testTreeSet.add(to));
        }
    }
}

Output of above program is 

Adding to the HashSet:
 Success
 Success
 Success
Copying to the TreeSet:
 Success
 Failure
 Failure

Can some one tell me why Tree set is behaving like this ?

Upvotes: 2

Views: 4163

Answers (3)

Dmitriy Popov
Dmitriy Popov

Reputation: 2350

Also the javadoc of java.util.Comparator explicitly describes this case and tells that Comparator for SortedSet must be consistent with equals:

For example, suppose one adds two elements a and b such that (a.equals(b) && c.compare(a, b) != 0) to an empty TreeSet with comparator c. The second add operation will return true (and the size of the tree set will increase) because a and b are not equivalent from the tree set's perspective, even though this is contrary to the specification of the Set.add method.

Upvotes: 0

Marius Loewe
Marius Loewe

Reputation: 236

"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". https://docs.oracle.com/javase/7/docs/api/java/util/TreeSet.html And your compareTo says they are all equal.

Upvotes: 7

afifit
afifit

Reputation: 106

The return value 0 for compareTo means the objects are equal, so e1.compareTo(e2) == 0 if and only if e1.equals(e2) == true.

TreeSet guarantees oredering so it uses the compare method, and HashSet does not so it uses the equals method. Try changing the compareTo method to a positive/negative number instead.

You can read more about the Compareable interface here.

Upvotes: 6

Related Questions