ConcurrentSkipListMap sorting: Can it be done by the value's compareTo?

Question

In a game, I'm trying to keep a list of users and have it sorted by score, so that I could query the list at any given time and return (for example) the top ten users by score. This list should be thread-safe. I envision using the userName string as a key and the value would be a User object which implements Comparable and has properties such as displayName and score. The User object would therefore have a compareTo method which would compare the score attribute to determine its position.

I'm looking at using a ConcurrentSkipListMap for this, but as best I can tell, the Map (as opposed to the Set) uses the key to sort. I'd like to have the list sorted by the score property of the User object, but still use a Map because I need to be able access any given user and modify their score attribute from a thread.

It doesn't seem that using my own Comparator for the key would solve my problem, as I doubt I'd have access to the associated value for comparison. I could use a ConcurrentSkipListSet but accessing the list to modify an individual user's score would be (I would imagine) an expensive operation (due to the need to iterate every time).

Would anyone be able to suggest how to accomplish this?

Answer 1

No, I don't think you can. The comparator used for ordering is the same one used for indexing. You will probably have to maintain 2 collections. One for keeping the ordering of user's scores the for referring to the users by name.

Answer 2

get(key) depends on the comparator (to be able to locate the key). You propose a comparator that would depend on get(key) (to access the mapped value of a key an compare based on that). That necessarily leads to infinite recursion and stack overflow (on the bright side, you are posting at the right website!!)

Answer 3

Michael is right, you can't have your cake and eat it too ;)

I think you have 3 choices:

1. Use a Map so that updates to a user's score are quick, and you pay the price when sorting to find the highest scores.
2. Use a SortedSet that sorts by score so that finding the highest scores is fast, but you must pay the price when updating user's scores
3. Maintain two data structures, so that you can have the best of 1 and 2. For example, you have your real data in a set sorted by score, but then also maintain a mapping of username to index into the set or similar. That way you always have the sorted scores, and updating a user's score is just a lookup, not a search. The price you pay for this is now you are maintaining some duplicate information in two places, and especially considering concurrent access, it can be tricky ensuring both places are always updated in synch.

I would not make assumptions about which is faster between 1 & 2. I would try them both out with your expected usage and measure to see what is worst.

If you are really only interested in the top n scores, then there is the possibility to just maintain that list separately. So have your map of username to score for everyone, but also maintain a small set of the top scores (and their users). Every time you add/update someone's score, just check the score against the top score list, and if it's bigger than the smallest one there, just add it and bump off the lower one. This is similar to suggestion 3 above, but is less overhead and perhaps easier to maintain.