Если в конструкторе TreeMap не предоставлен Comparator , который взаимно сравнивает ключи, ключи должны реализовывать Comparable .
См. Javadocs для TreeMap конструкторов для получения дополнительной информации: http://download.oracle.com/javase/6/docs/api/java/util/TreeMap.html
РЕДАКТИРОВАТЬ: Как @ MeBigFatGuy указывает, что для ключей настоятельно рекомендуется также переопределить equals () , таким образом, чтобы реализация была в соответствии со сравнением. Из TreeMap Javadoc:
Обратите внимание, что порядок, поддерживаемый отсортированной картой (независимо от того, предоставляется или нет явный компаратор) должен соответствовать равным , если эта отсортированная карта должна правильно реализовывать интерфейс Map. (См. Comparable или Comparator для точного определения в соответствии с равным .) Это так, потому что интерфейс Map определен в терминах операции equals, но карта выполняет все ключевые сравнения используя его метод compareTo (или compare), поэтому два ключа, которые считаются равными с помощью этого метода, с точки зрения отсортированной карты равны. Поведение отсортированной карты является четко определенным, даже если ее порядок не соответствует уравнениям; он просто не соблюдает общий контракт интерфейса Map.