Create a sorted by value Map before putting any data in it

Question

I know answer to this question has been provided in many variants but I couldn't find it for my specific query.

I want to have a map which is sorted by values and I need to get it created before I put data into it. I came up with below code to create it

private Map<String, Integer> mapUserScore = new ConcurrentSkipListMap<>(new Comparator<String>() {
    @Override
    public int compare(String o1, String o2) {
        int i1=mapUserScore.get(o2);
        int i2=mapUserScore.get(o1);
        if(mapUserScore.get(o2)!=null && mapUserScore.get(o1)!=null){
            int compare =  mapUserScore.get(o2)-(mapUserScore.get(o1));
            if(compare==0)compare=-1;
            return compare;
        }else
            return 0;
    }
});

So basically I want entries in map sorted by integer values in descending order so that highest scorers are on top. However upon doing this when the first key-value pair is inserted, the program exits with below exception

Exception in thread "Thread-0" java.lang.StackOverflowError
at java.util.concurrent.ConcurrentSkipListMap.comparable(ConcurrentSkipListMap.java:658)
at java.util.concurrent.ConcurrentSkipListMap.doGet(ConcurrentSkipListMap.java:821)
at java.util.concurrent.ConcurrentSkipListMap.get(ConcurrentSkipListMap.java:1626)

Upon tracing, I found that line int i1=mapUserScore.get(o2) results in this exception. Can anyone please help me to understand what could be the reason of stackoverflow here? I am thinking that because before any item is stored in the map, code is trying to obtain it by using get() method to sort it and hence it goes into some recursive calls and results in exception.

please see this link http://stackoverflow.com/questions/109383/how-to-sort-a-mapkey-value-on-the-values-in-java — krishnakumarp, Jul 18 '12 at 08:50

score 1 · Answer 1 · answered Jul 18 '12 at 08:56

1

If I understand correctly, you would like to be able to get the score associated to a name quickly (hence the need for a Map), and you would like to be able to iterate through tyhe name-score pairs with the highest scores first.

I would just use a HashMap<String, NameScore> (where the key is the name and the value is the name-score pair). This would give you O(1) lookups. And when you need to name-score pairs sorted by score, create a new ArrayList<NameScore> from the values() of the map, sort it, and return it.

answered Jul 18 '12 at 08:56

JB Nizet

678,734
91
1,224
1,255

well, sorry I should have mentioned the requirement more clearly. this map is going to store score for each user sorted by score in decreasing order. more than one player should be able to submit the score and at any time player should b e able to find out the top 10 scores. hence I need to have the structure sorted by score (which is Integer). so if use another HashMap, I got to have a separate method to calculate top scores (by creating HashMap)each time a request to find top score is received. that's why I want to store the player-score pair always sorted. – Eager Jul 18 '12 at 10:01
1

I don't see how that invalidate my solution. – JB Nizet Jul 18 '12 at 10:34
I don't say it invalidates your solution. but as I mentioned, there can be frequent requests to find out top scorers so if I create a new ArrayList from the values(), sort it and then return it in each request, will that be more efficient compared to having the map itself sorted by values in the first place? yet i am not sure if having created a sorted by values map initially is possible or not. – Eager Jul 18 '12 at 10:41
1

If it's really necessary (meaning: you have measurements showing that it's needed), you could cache a sorted list, invalidate it using some flag each time a score is modified or a player is added or removed, and re-sort the list when asked for it if it has been invalidated. Frankly, unless you have millions of players and ask for the top 10 many many times, I doubt it would make any significant difference. – JB Nizet Jul 18 '12 at 10:48

score 0 · Answer 2 · answered Jul 18 '12 at 08:45

0

The get() method uses the comparator to find the value. You can't use get in the comparator or your will get a stack over flow.

A simple work around is to include the score in the key and sort on that instead.

class NameScore implement Comparable<NameScore> {
     String name;
     int score;

}

BTW: When the comparator return 0 this means it is duplicate which is dropped. Unless you want only one name per score, you need to compare on the score AND the name.

answered Jul 18 '12 at 08:45

Peter Lawrey

525,659
79
751
1,130

i did not understand the work around completely. are you suggesting instead of having Map should I create a new class NameScore and have Map? – Eager Jul 18 '12 at 10:34
1

Yes, That will allow you to sort on key and avoid dropping duplicate scores (for different people) – Peter Lawrey Jul 18 '12 at 10:36

Create a sorted by value Map before putting any data in it

2 Answers2