0

The TreeMap structure is a classic map structure with keys sorted by their natural order. For example, with the following codes:

Map<String, Integer> map = new TreeMap<>();
map.put("apple", 100);
map.put("orange", 10);
map.put("banana", 5);

If I want to print the map, like:

System.out.println(map);

Then the console will output (with natural order of the key):

{apple=100, banana=5, orange=10}

My question is: is there any Map structure available (UnknownMap) that could automatically sort the key by the value? If we have such structure, if we revise the codes to:

Map<String, Integer> map = new UnknownMap<>();
map.put("apple", 100);
map.put("orange", 10);
map.put("banana", 5);
System.out.println(map);

The console will output:

{banana=5, orange=10, apple=100}

Note: this question is not asking how to sort a map. Instead, this is to ask a specific sorted map implementation that efficiently do the sorting by value with any changes to the map, such as put, remove, etc.

Mark Rotteveel
  • 100,966
  • 191
  • 140
  • 197
user16830227
  • 76
  • 6
  • Please let me know if my question is not clear enough. Thanks! – user16830227 Sep 08 '21 at 18:29
  • You should probably read this: [**How do I ask a good question?**](https://stackoverflow.com/help/how-to-ask) It says, among othrer things, "Search, and research ...and keep track of what you find." That's [more than a bit relevant here...](https://www.google.com/search?q=java+sorted+map) – Andrew Henle Sep 08 '21 at 18:32
  • 1
    @Joe That is not a duplicate. **Sorting** a `Map` is not the same as a **sorted** `Map`. – Andrew Henle Sep 08 '21 at 18:34
  • @Joe, yeah, that could be a way to so. However, it is better to make automatically and efficiently sorting for the whole map with any insert, update, and remove. – user16830227 Sep 08 '21 at 18:37
  • 2
    There no any Map implementation in java which by default sort by Value. We need to do manual code to make them sort by value like by passing comparator (which sorts by value) to TreeMap constructor like `Map sortedByValues = new TreeMap(valueComparator);` – navnath Sep 08 '21 at 18:42
  • @Andrew Henle, yes, it is more like a standalone map structure. Maybe, someone implemented it somewhere else, but is not available at Java.Util. – user16830227 Sep 08 '21 at 18:43
  • @NavnathJadhav, the comparator passed in `TreeMap` constructor is applied to keys anyway. [JavaDoc:](https://docs.oracle.com/javase/7/docs/api/java/util/TreeMap.html#TreeMap(java.util.Comparator)) `public TreeMap(Comparator super K> comparator)` Constructs a new, empty tree map, ordered according to the given comparator. All keys inserted into the map must be _mutually comparable_ by the given comparator. – Nowhere Man Sep 08 '21 at 18:51
  • The solution is simply: `map.entrySet().stream().sorted(Map.Entry.comparingByValue())`. But, if you need a mutable structure with efficient operations (add, delete, search, ...) both, on keys and value you are talking about a simple indexed database table with an additional indexed field (the value). – josejuan Sep 08 '21 at 19:02
  • @AlexRudenko But we could build some logic to Sort Map by value like at https://beginnersbook.com/2014/07/how-to-sort-a-treemap-by-value-in-java – navnath Sep 08 '21 at 19:10
  • 2
    This is a duplicate of this post https://stackoverflow.com/questions/16545871/maintain-sortedmap-by-value – ronpi Sep 08 '21 at 19:33

1 Answers1

0

Maintaining a sorted map by value is very not trivial, and would definitely require to adjust existing data structures. The entries, keys and values fields, that are required by the Map interface, are expected to be consistent with their order, and this is not trivial to get all of them sorted by value, and at least would require to override these fields in existing classes. Take for example the TreeMap class. The keys are stored in a tree data-structure, and the order of all three fields is according to the keys inserted to the tree. Also you cannot override the `Comparator of the tree to ignore the key itself, because some fundamental map properties of this class depends on that the tree compare between keys and not values.

This is as opposed to just sorting the map entries when it requires which is much simpler task. If you need to frequently use the sorted map entries, and the map tends to be modified between such usages, than it worth maintaining such data structure, otherwise you should just sort the entries and store them separately for future use.

In you you have decided to maintain the sorted map by value, you will probably need to implement it yourself. Try using the answers from this post

ronpi
  • 470
  • 3
  • 8