Why does TreeSet throw a ClassCastException?

Question

I am trying to add two 'Employee' objects to a TreeSet:

Set<Employee> s = new TreeSet<Employee>();
s.add(new Employee(1001));
s.add(new Employee(1002));

But it throws a ClassCastException:

Exception in thread "main" java.lang.ClassCastException: Employee cannot be cast to java.lang.Comparable
    at java.util.TreeMap.put(TreeMap.java:542)
    at java.util.TreeSet.add(TreeSet.java:238)
    at MyClient.main(MyClient.java:9)

But if I add only one object to the TreeSet:

Set<Employee> s = new TreeSet<Employee>();
s.add(new Employee(1001));

Or if I use a HashSet instead:

Set<Employee> s = new HashSet<Employee>();
s.add(new Employee(1001));
s.add(new Employee(1002));

Then it is successful. Why does the exception happen and how do I fix it?

Solution 1

Either Employee has to implement Comparable, or you need to provide a comparator when creating the TreeSet.

This is spelled out in the documentation for SortedSet:

All elements inserted into a sorted set must implement the Comparable interface (or be accepted by the specified comparator). Furthermore, all such elements must be mutually comparable: e1.compareTo(e2) (or comparator.compare(e1, e2)) must not throw a ClassCastException for any elements e1 and e2 in the sorted set. Attempts to violate this restriction will cause the offending method or constructor invocation to throw a ClassCastException.

If you don't fulfil these requirements, the sorted set won't know how to compare its elements and won't be able to function.

Solution 2

TreeSet requires elements to implement the Comparable interface if a custom Comparator is not set. HashSet uses the equals/hashCode contract instead.

You can add only one element into TreeSet which does not implement Comparable because it does not need to be compared with other elements.

Take a look at the TreeMap.put(K key, V value) source code and you'll clearly see the reasons behind all your questions (TreeSet is based on TreeMap, hence the source reference).

Solution 3

From TreeSet#add(E) JavaDoc:

Throws: ClassCastException - if the specified object cannot be compared with the elements currently in this set

Basically what you need is to let Employee implement Comparable or provide a Comparator to the TreeSet object.

If you check TreeMap code you will see that if the comparator wasn't found within the Map object, it will try to cast the key (your Employee object) directly to Comparator:

...
Comparable<? super K> k = (Comparable<? super K>) key;
...

Comments

[Rais Alam]

Is implementation of comprable Interface mendatory?

[NPE]

@FireFly: No, it's not. You can provide a comparator. See my answer.

[Rais Alam]

Ok so either Employee must implement comparable or i need to create an external comparator am I right?

[Rais Alam]

But in present case Employee class does not implements comparable and there is no External comparator. Every thing works fine when i ad one element. Problem starts when I add second element. Question is if the scenario you described is mandatory then why compiler compiles that program.

[NPE]

@FireFly: It's mandatory, but is not enforced until the set actually needs to compare elements (which happens when you try to add the second element).

[LeleDumbo]

@FireFly: Without the external comparator, the class assumes the specialization parameter to implement Comparable interface. Either one must exist, but the compiler can't force such a constraint because it's not possible to do so at compile time.

[vijayraj34]

@NPE Thanks for the answer explanation. I was asked in an interview and i failed to answer.

[charu]

Employee eobj1 = new Employee(3); Employee eobj2 = new Employee(2); //o/p : 3 only