java concurrent map sorted by value

Question

I'm looking for a way to have a concurrent map or similar key->value storage that can be sorted by value and not by key.

So far I was looking at ConcurrentSkipListMap but I couldn't find a way to sort it by value (using Comparator), since compare method receives only the keys as parameters.

The map has keys as String and values as Integer. What I'm looking is a way to retrieve the key with the smallest value(integer).

I was also thinking about using 2 maps, and create a separate map with Integer keys and String values and in this way I will have a sorted map by integer as I wanted, however there can be more than one integers with the same value, which could lead me into more problems.

Example

"user1"=>3 "user2"=>1 "user3"=>3

sorted list: "user2"=>1 "user1"=>3 "user3"=>3

Is there a way to do this or are any 3rd party libraries that can do this?

Thanks

Answer 1

To sort by value where you can have multiple "value" to "key" mapping, you need a MultiMap. This needs to be synchronized as there is no concurrent version.

This doesn't meant the performance will be poor as that depends on how often you call this data structure. e.g. it could add up to 1 micro-second.

Answer 2

The principle of a ConcurrentMap is that it can be accessed concurrently - if you want it sorted at any time, performance will suffer significantly as that map would need to be fully synchronized (like a hashtable), resulting in poor throughput.

So I think your best bet is to return a sorted view of your map by putting all elements in an unmodifiable TreeMap for example (although sorting a TreeMap by values needs a bit of tweaking).

Answer 3

I recently had to do this and ended up using a ConcurrentSkipListMap where the keys contain a string and an integer. I ended up using the answer proposed below. The core insight is that you can structure your code to allow for a duplicate of a key with a different value before removing the previous one.

Atomic way to reorder keys in a ConcurrentSkipListMap / ConcurrentSkipListSet?

The problem was to keep a dynamic set of strings which were associated with integers that could change concurrently from different threads, described below. It sounds very similar to what you wanted to do.

Is there an embeddable Java alternative to Redis?

Here's the code for my implementation:

https://github.com/HarvardEconCS/TurkServer/blob/master/turkserver/src/main/java/edu/harvard/econcs/turkserver/util/UserItemMatcher.java