Java TreeMap with keys that do not implement Comparable [duplicate]

Question

I noticed that I can create an instance of the Java 8 TreeMap<K,V> (https://docs.oracle.com/javase/8/docs/api/java/util/TreeMap.html) as

TreeMap<Object, Integer> foo = new TreeMap<Object, Integer>();

But why does this not generate a compilation error, seeing as Object does not implement Comparable, and I did not supply a Comparator? How is the TreeMap supposed to sort the keys without any way to know what order they're in?

Answer 1

Why no compile time error

TreeMap could have been declared as:

public class TreeMap<K extends Comparable<? super K>,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable
{

Note the K extends Comparable<? super K> constraint. This would totally disallow you from using non-Comparable types such as Object as the key type. However, sometimes you do want to use a non-Comparable type, and provide an explicit comparator. You'd totally disallow those cases, which are quite valid, if you added that constraint.

What about only adding the constraint when you are not providing a comparator explicitly, i.e. making the parameterless constructor available only when the key type implements Comparable? There are languages that have syntax that allows you to do this. Unfortunately, Java isn't one of those languages :(

In the end they decided that it was better to allow you to always use non-Comparable types as the key type (and crash at runtime), than to not allow you to use custom comparators + non-Comparable key types.

Why your code does not crash at runtime

(Though you didn't specifically ask about this, I thought I should explain this too, because you seem to think that Java still has some way of sorting the non-Comparable objects, presumably your code didn't crash. The truth is, Java doesn't know how to sort your non-Comparable objects.)

Your code only creates the map. At runtime, the generics are erased, so it can't possibly know that you are creating a map with non-Comparable keys. It's only when you add non-Comparable keys into it, that it crashes:

TreeMap<Object, Integer> foo = new TreeMap<Object, Integer>();
foo.put(new Object(), 1); // crashes

Plus, you can still add comparable keys to a TreeMap<Object, Integer>.

Answer 2

Use another constructor that requires Comparator.

• public TreeMap(Comparator<? super K> comparator)

Constructs a new, empty tree map, ordered according to the given comparator. All keys inserted into the map must be mutually comparable by the given comparator

For example, I compare Object instances based on their toString method, but the final implementation is up to you. Both comparators below are the same:

• Comparator<Object> comparator = (l, r) -> l.toString().compareTo(r.toString());
  

• Comparator<Object> comparator = Comparator.comparing(Object::toString);
  

Pass the Comparator into the constructor:

TreeMap<Object, Integer> foo = new TreeMap<>(comparator);