Un HashMap propiamente no se puede ordenar, pero existen estructuras que permiten la ordenación.
Si lo que necesitas es el orden de inserción de un HashMap, puedes o bien guardar la clave en un array y así no perder la ordenación, o más fácil utilizando LinkedHashMap que ya lo hace por ti.
Por otro lado, si lo que quieres es ordenar las claves (con sort por ejemplo), con algún criterio (por ejemplo alfabéticamente), puedes obtener todas las claves con KeySet() en un set de datos, luego convertir este set a listado y ordenarlo como necesites. Un ejemplo:
private Map<String, String> miMap = new HashMap<String, String>();
miMap.put("una clave", "un valor"); // Añadimos las claves que queramos
Set setDeClaves = miMap.keySet()
List miLista = new ArrayList(setDeClaves);
Collections.sort(miLista);