I have a problem where I am using a Map<Double,String> to store values that are returned in that form. The issue is, there are possible instances that violate this.

["23.2,Name","23.2,Name2","50.0,Name3"] for instance is something that can occur with my current algorithm because it computes distance from one city to another. The reason why I want it Double,String is for sorting reasons so my question is:

Is it possible to make it work like this ["23.2,Name","23.2,Name2"] or to have it like ["Name,23.2","Name2,23.2","Name3,50.0"] and sort based off the double?

CodePudding user response：

This seems to be an issue related to sorting algorithm stability; however, I also believe there could be a small logical error as well, which we may look at as well.

Let's have a quick look at what stable sorting is, and if we can work out the problem posted in the question.

Stable Sort

There is a very beautiful explanation of this concept here: Stability in Sorting Algorithms

In simple words, when a sorting algorithm deals with duplicate keys by maintaining the order in which they appear, it is called a stable sort. If the algorithm can mess up the order when duplicate keys come up, it is an unstable sort.

In your question, it has been stated that you wish to use duplicate keys, and this means you would require a stable sorting algorithm to handle it.

However

Possible Logical Error

There may be a flaw in the representation of data which has been adopted here. The map has been configured as Double->String, which is fine.

The problem arises with the fact that a map can have only 1 key of a certain value. In the rare case that 23.2 happens to be the exact key value for 2 strings, the java map would simply replace "Name" with "Name2" instead of making 2 key-value pairs, as depicted in the question.

Map in Question:

{23.2 : "Name", 23.2 : "Name2", 50.0 : "Name3"}

Map that would actually be made in Java:

{23.2 : "Name2", 50.0 : "Name3"}    // "Name" is replaced by "Name2"

Possible solutions

1. Use a different mapping approach, or make sure that 2 keys are never the same even before adding them to the map.
2. Use a Double->List[String] instead of Double->String, and in the case that there are more than one Strings for a particular key, extend the list instead of making a new key value pair.

I hope this resolves your query, at least to some extent. In case there is something unclear, let me know here at StackOverflow and I will try my best to reply as soon as possible.

CodePudding user response：

A map can't contain multiple entries with the same key.

You might to use List<String> as a type of values, or else you could lose the information.

In order to maintain the order of keys, you need to use TreeMap which will sort the keys according to their natural order if comparator wasn't provided when map was instantiated (for that the type of keys must implement Comparable interface which is the case for Double).

You can populate the map in the following way:

NavigableMap<Double, List<String>> distToCity = new TreeMap<>(); // "23.2,Name","23.2,Name2","50.0,Name3"
 
//        distToCity.computeIfAbsent(23.2, k -> new ArrayList<>()).add("Name"); does the same as two lines below
distToCity.putIfAbsent(23.2, new ArrayList<>());
distToCity.get(23.2).add("Name");
distToCity.get(23.2).add("Name2");
    
distToCity.putIfAbsent(50.0, new ArrayList<>());
distToCity.get(50.0).add("Name3");
    
System.out.println(distToCity);

Output (both values "Name" and "Name2" would be preserved and mapped to the same key 23.2)

{23.2=[Name, Name2], 50.0=[Name3]}

Another option is store these pairs of values objects. For that you need to define a class, let's say Pair.

public class Pair<K, V> {
    private K key;
    private V value;
    
    // constructor, getters, equals/hashCode, toString()
}

These object could be merely stored in a list, in order sort it you have to define the comparator, which will compare object by key:

Comparator.comparingDouble(Pair::getKey)

Example with a list of pairs.

List<Pair<Double, String>> pairs = new ArrayList<>();
pairs.add(new Pair<>(23.2, "Name"));
pairs.add(new Pair<>(23.2, "Name2"));
pairs.add(new Pair<>(50.0, "Name3"));
        
Comparator<Pair<Double, String>> pairComparator = Comparator.comparingDouble(Pair::getKey);
pairs.sort(pairComparator);
System.out.println(pairs);

Output

[Pair{key=23.2, value=Name}, Pair{key=23.2, value=Name2}, Pair{key=50.0, value=Name3}]

CodePudding user response：

As already pointed out by others, we cannot have duplicate key in Map, Can you use Map<String, Double> and sort it by value as i can see city name will be unique like Name, Name2, Name3?

final Map<String, Double> sortedByValue = distToCity.entrySet()
                .stream()
                .sorted(Map.Entry.comparingByValue())
                .collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue, (e1, e2) -> e1, LinkedHashMap::new));

or other option is to have Map<Double,List>

Hope it helps