The preceding examples sort the given map, and the result is also a map. If all we need is the sorted keys (and we don't care about the values) or vice versa, then we can rely on a List created via Map.keySet() for keys, and via Map.values() for values:

public static <K extends Comparable, V> List<K>
    sortByKeyList(Map<K, V> map) {

  List<K> list = new ArrayList<>(map.keySet());
  Collections.sort(list);

  return list;
}

public static <K, V extends Comparable> List<V>
    sortByValueList(Map<K, V> map) {

  List<V> list = new ArrayList<>(map.values());
  Collections.sort(list);

  return list;
}

Now, let's sort our map:

// [delicious, famous, refreshing]
List<String> sortedKeys = Maps.sortByKeyList(melons);

// [Cantaloupe(1500g), Apollo(3000g), Jade Dew(3500g)]
List<Melon> sortedValues = Maps.sortByValueList(melons);

If duplicate values are not allowed, then you have to rely on an implementation using SortedSet:

SortedSet<String> sortedKeys = new TreeSet<>(melons.keySet());
SortedSet<Melon> sortedValues = new TreeSet<>(melons.values());