sort concurrent map entries by value

Question

Is there any way to create a thread-safe implementation of Map that maintains it's entries sorted by value? I know I can create a thread-safe Map like this

ConcurrentMap<String, Double> rankings = new ConcurrentHashMap<String, Double>();

And I can then get the entries sorted by value by passing it to a utility method like this:

public static <K, V extends Comparable<? super V>> Map<K, V> sortByValue(Map<K, V> map) {
    List<Map.Entry<K, V>> list = new LinkedList<Map.Entry<K, V>>(map.entrySet());
    Collections.sort(list, new Comparator<Map.Entry<K, V>>() {
        @Override
        public int compare(Map.Entry<K, V> o1, Map.Entry<K, V> o2) {
            return (o1.getValue()).compareTo(o2.getValue());
        }
    });

    Map<K, V> result = new LinkedHashMap<K, V>();
    for (Map.Entry<K, V> entry : list) {
        result.put(entry.getKey(), entry.getValue());
    }
    return result;
}

But what I'm looking for is a thread-safe Map that maintains the entries sorted by value, so that I don't have to call a method such as the above after every insertion/removal in order to keep the entries sorted by value. I guess I'm looking for an implementation that combines the behavior of ConcurrentHashMap and LinkedHashMap, but haven't found one yet.

ConcurrentSkipListMap almost provides what I want, but it only seems to support sorting by key value.

In your use-case, can you restrict the problem to *unique* values, or do you sometimes get duplicate values? If you do have duplicate values, do you have further sorting constraints? — Dilum Ranatunga, May 09 '11 at 21:07
Also, please clarify -- do you wanted *sorted* or *ordered*? A LinkedHashMap gives you ordered, but not sorted. — Dilum Ranatunga, May 09 '11 at 21:08
@Dilum I could eliminate the possibility of duplicate map values if necessary — Dónal, May 09 '11 at 21:39
Suppose you add "three", "two", "one" in that order to an empty LinkedHashSet. If you iterate over the elements, they will return in that same order. That is *ordered* -- they return in some predictable, meaningful manner. If you added the same to a TreeSet using the default comparator, they would return as "one", "three", "two". Once again predictable and meaningful, but also *sorted* because the insertion order has no bearing. If you were to add the elements to a HashSet, the ordering of the elements would not be predictable. — Dilum Ranatunga, May 09 '11 at 21:55

score 2 · Answer 1 · answered May 09 '11 at 21:48

Consider building a composite data structure for this. At a high level, do the following.

First, implement Map.Entry to keep key-value pairs. The pair's ordering would be first by value, and then by key.

private static class InternalEntry<K extends Comparable<K>,
                                   V extends Comparable<V>>
        implements Comparable<InternalEntry<K, V>>,
                   Map.Entry<K, V> {
    private final K _key;
    private final V _val;

    InternalEntry(K key, V val) {
        _key = key;
        _val = val;
    }

    public K getKey() {
        return _key;
    }

    public V getValue() {
        return _val;
    }

    public V setValue(V value) {
        throw new UnsupportedOperationException();
    }

    public int compareTo(InternalEntry<K, V> o) {
        int first = _val.compareTo(o._val);
        if (first != 0) {
            return first;
        }
        return _key.compareTo(o._key);
    }
}

The entire entry can be used as the key of an ordered map.

But that map does not support efficient lookup of value by key. To achieve that, introduce another map, which maps keys to entries.

The composite structure looks like this:

class OrderedByValue<K extends Comparable<K>, V extends Comparable<V>> {
    private final Map<InternalEntry<K, V>, Boolean> _ordering = 
        new TreeMap<InternalEntry<K, V>, Boolean>();

    private final Map<K, InternalEntry<K, V>> _lookup = 
        new HashMap<K, InternalEntry<K, V>>();

    public V put(K key, V val) {
        InternalEntry<K, V> entry = new InternalEntry<K, V>(key, val);
        InternalEntry<K, V> old = _lookup.put(key, entry);
        if (old == null) {
            _ordering.put(entry, Boolean.TRUE);
            return null;
        }
        _ordering.remove(old);
        _ordering.put(entry, Boolean.TRUE);
        return old.getValue();
    }

    @SuppressWarnings({"unchecked"})
    public Iterable<Map.Entry<K, V>> entrySet() {
        Iterable entries = Collections.unmodifiableSet(_ordering.keySet());
        return (Iterable<Map.Entry<K, V>>) entries;
    }
}

Note that I've not supplied all the necessary code to implement a full Map -- let me know if you need help with the other methods.

You also need to do some special case code in the InternalEntry's comparison implementation if null keys/values need to be supported.

@Dave, I've left it up to you to switch TreeMap, LinkedHashMap with their concurrent brethren. — Dilum Ranatunga, May 09 '11 at 21:56

sort concurrent map entries by value

1 Answers1

Linked