A quick solution to sorting a Map relies on TreeMap. By definition, the keys in TreeMap are sorted by their natural order. Moreover, TreeMap has a constructor of the TreeMap​(Map<? extends K,​? extends V> m) type:

public static <K, V> TreeMap<K, V> sortByKeyTreeMap(Map<K, V> map) {

  return new TreeMap<>(map);
}

And calling it will sort the map by key:

// {delicious=Apollo(3000g), 
// famous=Cantaloupe(1500g), refreshing=Jade Dew(3500g)}
TreeMap<String, Melon> sortedMap = Maps.sortByKeyTreeMap(melons);