Desde el JavaDoc de TreeMap:

Tenga en cuenta que el ordenamiento mantenido por un mapa ordenado (ya sea que se proporcione o no un comparador explícito) debe ser coherente con iguales si este mapa ordenado debe implementar correctamente la interfaz del Mapa. (Consulte Comparable o Comparator para una definición precisa de consistente con iguales). Esto se debe a que la interfaz del Mapa se define en términos de la operación de iguales, pero un mapa realiza todas las comparaciones de claves utilizando su método compareTo (o compare), por lo que dos claves que se consideran iguales por este método son, desde el punto de vista del mapa ordenado, iguales. El comportamiento de un mapa ordenado está bien definido incluso si su orden es inconsistente con los iguales; simplemente no cumple con el contrato general de la interfaz del Mapa.

¿Puede alguien dar un ejemplo concreto para demostrar el problema que podría ocurrir si el pedido no es consistente con los iguales? Tomemos, por ejemplo, la clase definida por el usuario que tiene un orden natural, es decir, implementa Comparable. ¿También todas las clases internas en JDK mantienen este invariante?