How to sort Map values by key in Java?

Short answer
Use a TreeMap. This is precisely what it’s for.
If this map is passed to you and you cannot determine the type, then you can do the following:
SortedSet keys = new TreeSet<>(map.keySet());
for (String key : keys) {
String value = map.get(key);
// do something
}

This will iterate across the map in natural order of the keys.

Longer answer
Technically, you can use anything that implements SortedMap, but except for rare cases this amounts to TreeMap, just as using a Map implementation typically amounts to HashMap.
For cases where your keys are a complex type that doesn’t implement Comparable or you don’t want to use the natural order then TreeMap and TreeSet have additional constructors that let you pass in a Comparator:
// placed inline for the demonstration, but doesn’t have to be a lambda expression
Comparator comparator = (Foo o1, Foo o2) -> {
…
}

SortedSet keys = new TreeSet<>(comparator);
keys.addAll(map.keySet());

Remember when using a TreeMap or TreeSet that it will have different performance characteristics than HashMap or HashSet. Roughly speaking operations that find or insert an element will go from O(1) to O(Log(N)).
In a HashMap, moving from 1000 items to 10,000 doesn’t really affect your time to lookup an element, but for a TreeMap the lookup time will be about 3 times slower (assuming Log2). Moving from 1000 to 100,000 will be about 6 times slower for every element lookup.

Assuming TreeMap is not good for you (and assuming you can’t use generics):
List sortedKeys=new ArrayList(yourMap.keySet());
Collections.sort(sortedKeys);
// Do what you need with sortedKeys.