Why does TreeSet throw a ClassCastException?

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?

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.

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

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