Raff, pensando nas interfaces em geral (Map e Set), você pode ter chaves/valores com tipos diferentes.
Apenas nos casos das implementações TreeSet e TreeMap é que há essa restrição. Isso porque eles utilizam o método compareTo() da clase da chave/valor (que por sua vez deve implementar a interface Comparable) pra poder fazer a ordenação (ou o método compare, caso tenha sido informado umComparator no momento da instanciação da coleção). E nesse método, dependendo da implementação, ele tenta fazer um cast para o tipo da chave/valor (esse cast existe pelo menos nas classes mais comuns, String, Integer, Long, etc…) . Então, quando os tipos são diferentes, acaba sendo lançado um ClassCastException.
Já nos casos simples, HashSet, LinkedHashSet, HashMap, Hashtable essa exceção não é lançada pois não existe essa tentativa de cast e, por isso, não há restrição entre os tipos das chaves/valores.
Isso significa que, na verdade, embora estejamos falando que as classes da chave/valor devem ter o mesmo tipo para nao ser lancado ClassCastException em tempo de execucao, isso não eh 100% correto. Isso soh eh verdade se a implementacao do metodo compare da classe que esta sendo inserida tenta fazer um cast (o que acontece para a maioria das classes testadas no exame) ou se o Comparator informado no momento q instanciou a coleção tenta fazer o cast.
Isso quer dizer que se vc criar duas classes diferentes que implementam Comparable e simplesmente retornam um numero fixo 1, por exemplo, e vc tentar colocar elementos dessa classe em um TreeSet, mesmo sendo de tipos diferentes, não será lançado ClassCastException.