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?

Answer 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.

Answer 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).