Once we create a Stream for a map, we can easily sort it by means of the Stream.sorted() method with or without a Comparator. This time, let's use a Comparator:

public static <K, V> Map<K, V> sortByKeyStream(
    Map<K, V> map, Comparator<? super K> c) {

  return map.entrySet()
    .stream()
    .sorted(Map.Entry.comparingByKey(c))
    .collect(toMap(Map.Entry::getKey, Map.Entry::getValue,
      (v1, v2) -> v1, LinkedHashMap::new));
}

public static <K, V> Map<K, V> sortByValueStream(
    Map<K, V> map, Comparator<? super V> c) {

  return map.entrySet()
    .stream()
    .sorted(Map.Entry.comparingByValue(c))
    .collect(toMap(Map.Entry::getKey, Map.Entry::getValue,
      (v1, v2) -> v1, LinkedHashMap::new));
}

We need to rely on LinkedHashMap instead of HashMap. Otherwise, we cannot preserve the iteration order.

Let's sort our map as follows:

// {delicious=Apollo(3000g), 
//  famous=Cantaloupe(1500g), 
//  refreshing=Jade Dew(3500g)}
Comparator<String> byInt = Comparator.naturalOrder();
Map<String, Melon> sortedMap = Maps.sortByKeyStream(melons, byInt);

// {famous=Cantaloupe(1500g), 
//  delicious=Apollo(3000g), 
//  refreshing=Jade Dew(3500g)}
Comparator<Melon> byWeight = Comparator.comparing(Melon::getWeight);
Map<String, Melon> sortedMap 
  = Maps.sortByValueStream(melons, byWeight);