Ordenar pela chave

SortedSet<String> keys = new TreeSet<String>(myHashMap.keySet());

 

Ordernar pelo valor

SortedSet<String> values = new TreeSet<String>(myHashMap.values());

 

Observação: Se o tipo for uma classe você deve implementar um Comparable